1213번 : 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

 

 

문제

 

 

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        int alpha[] = new int [26];

        for(int i=0;i<input.length();i++) {
            alpha[input.charAt(i)-65]+=1;
        }

        int isOne=0;
        for(int i=0;i<26;i++) {
            if(alpha[i]%2!=0) isOne++;
        }

        if(isOne>1) {
            System.out.println("I'm Sorry Hansoo");
        }
        else {
            String finish="";
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<26;i++) {
                int x = alpha[i]/2;
                for(int j=0;j<x;j++) {
                    sb.append((char)(i+65));
                }
            }
            String front = sb.toString();
            finish+=front
			
            for(int i=0;i<26;i++) {
            	//mid 넣기
                if(alpha[i]%2!=0){
                    finish+=(char)(i+65);
                    break;
                }
            }
            
            String end = sb.reverse().toString();
            finish+=end
            bw.write(finish); bw.flush();
        }
    }
}

 

 

해결방법

어떻게 풀지 계속 고민하다가 생각해 낸 방법은

1. 입력받은 문자열의 알파벳 수만큼 각각 배열에 저장
2. 짝수개인 알파벳으로 펠린드롬 만들기
   1. (알파벳 개수)/2개 만큼 문자열에 담기

이렇게밖에 생각을 하지 못했고 홀수를 어떻게 처리해야 할지 감이 안 와서 약간의 구글링을 하였다.

구글링을 한 결과는 개수가 홀수개인 알파벳은 1개 이하이어야만 펠린드롬을 만들 수 있다는 것을 알았다. 그러므로 펠린드롬을 만들 수 없는 경우를 찾을 수 있었다. 

그리고 홀수개는 정확히 반으로 나눌 수 없으므로 "(알파벳 개수)/2 만큼 문자열에 담기"는 짝수개일 때만 해야 한다고 생각했는데 홀수개도 /2 해서 넣어도 된다. 왜냐하면 어차피 홀수개인 알파벳은 1개이기에 (알파벳 개수)/2 했을 때 남는 1개는 가운데에다 넣으면 되기 때문이다.

 

다시 정리를 해보면

1. 입력받은 문자열의 알파벳 수만큼 각각 배열에 저장
2. 홀수개를 가지는 알파벳의 수 세기
   1. 1개 이상이면 "I'm Sorry Hansoo" 출력 후 종료
3. 펠린드롬 만들기
   1. 모든 알파벳에 대하여 (알파벳 개수)/2개만큼 문자열에 담기 (front)
   2. 홀수개인 알파벳 1개 문자열에 담기 (mid)
   3. front를 reverse 하여 문자열에 담기 (end)
   4. front, mid, end를 이어 붙여 출력 후 종료

며칠 뒤에 다시 한번 풀어봐야겠다.