[백준] 1213번

사이트

 

https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 

문제

 

분석

처음에 어려웠는데 계속 생각하다 보면 간단한 문제다. 

 

int[] alphabet = new int[26];
for (int i = 0; i < sentence.length(); i++) {
    alphabet[sentence.charAt(i) - 'A'] += 1;
}

- 대문자만 입력되어야한다. 그래서 입력한 문장에 따라서 알파벳 개수를 담는 알파벳 배열을 만들었다. 

- 아스키 코드를 활용해서 위와 같이 갯수를 저장할 수 있다. 

 

생각을 좀 해보면 홀 수 갯수인 알파벳이 2개 이상있으면 그 결과는 팰린드룸을 만들지 못한다. 

그래서 홀 수 갯수인 알파벳이 있으면 하나만 갖고가서 해당 문장에 중간위치에 넣으면 된다. 

 

그리고 사전순으로 젤 빠른것이 출력이 된다. 이게 굉장히 핵심 문장이다.

 

for (int i = 0; i < alphabet.length; i++) {
    if (alphabet[i] != 0) {
        num = alphabet[i];
        int size = num / 2;
        for (int front = 0; front < size; front++) {
            result[front_p] = (char) ((char) i + 'A');
            front_p++;
        }
        for (int rear = size; rear > 0; rear--) {
            result[rear_p] = (char) ((char) i + 'A');
            rear_p--;
        }
        if (num % 2 == 1) {
            int middle = sentence.length() / 2;
            result[middle] = (char) ((char) i + 'A');
            if (cnt != 0) {
                System.out.println("I'm Sorry Hansoo");
                cnt = 2;
                break;
            }
            cnt = 1;
        }
    }
}

- 알파벳 순으로 배열이 저장되어 있으므로  해당 알파벳을 꺼내서 앞쪽으로 배치해두는 것이다!

(ex) A가 7개면 AAA    A   AAA)

- 즉 A가 7개면 2로 나누어서 3개는 앞쪽 3개는 뒤쪽 나머지가 있으면 중간에 끼어 넣으면 된다!  

- 위 코드 토대로 출력배열 result를 만들어서 저장한 것인데 앞쪽 3개, 뒤쪽 3개를 넣을 때 위치를 조정해야되서 

front_p, rear_p를 만든 것이다. 

- 만약에 홀 수 알파벳이 2개가 들어오면 cnt는 자동적으로 첫번째 홀수를 제외한 0이 아니기때문에 오류메시지가 뜬다. 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String sentence = String.valueOf(br.readLine());
        int[] alphabet = new int[26];
        for (int i = 0; i < sentence.length(); i++) {
            alphabet[sentence.charAt(i) - 'A'] += 1;
        }
        char[] result = new char[sentence.length()];
        int front_p = 0;
        int cnt = 0;
        int rear_p = sentence.length() - 1;
        cnt = solution(sentence, alphabet, result, front_p, cnt, rear_p);
        if (cnt != 2) {
            for (char c : result) {
                System.out.print(c);
            }
        }
    }

    private static int solution(String sentence, int[] alphabet, char[] result, int front_p, int cnt, int rear_p) {
        int num;
        for (int i = 0; i < alphabet.length; i++) {
            if (alphabet[i] != 0) {
                num = alphabet[i];
                int size = num / 2;
                for (int front = 0; front < size; front++) {
                    result[front_p] = (char) ((char) i + 'A');
                    front_p++;
                }
                for (int rear = size; rear > 0; rear--) {
                    result[rear_p] = (char) ((char) i + 'A');
                    rear_p--;
                }
                if (num % 2 == 1) {
                    int middle = sentence.length() / 2;
                    result[middle] = (char) ((char) i + 'A');
                    if (cnt != 0) {
                        System.out.println("I'm Sorry Hansoo");
                        cnt = 2;
                        break;
                    }
                    cnt = 1;
                }
            }
        }
        return cnt;
    }

}

 

 

결과

 

느낀점

거의 2시간이 걸린 문제로 처음에는 경우의 수를 브루포토스 알고리즘 처럼 모두 만들어 중복되는 것으로 set으로 걸러낸뒤 할려했으나 필자는 재귀함수 부분이 약하고 너무 애먹어서 여기서 1시간을 날렸다. 그 후 천천히 분석해서 다음과 같은 결과를 만들었다. 딱 실버3인 문제였다.