BOJ - 팰린드롬 만들기 1213번 (JAVA)

❓ 문제 - 백준 팰린드롬 만들기 1213번 - JAVA 풀이법

 

출처 

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

1213번: 팰린드롬 만들기

 

 

📝 문제해결법

1. 이 문제는 Implementation(구현) - 문자열 처리로 알고리즘을 풀었다.

• 처음 받은 문자열에 대해 알파벳 나온 횟수를 배열에 담는다.
• 만약 받은 문자열의 길이가 홀수이면서, 알파벳 출현 횟수가 홀수개 나온 알파벳이 1 이상이면 팰린드롬을 만들 수 없다.
• 만약 받은 문자열의 길이가 짝수이면서, 알파벳 출현 횟수가 홀수개 나온 알파벳이 0이상이면 팰린드롬을 만들 수 없다.
• 즉, 팰린드롬은 문자열의 길이가 짝수이면서 알파벳들이 다 짝수개 존재하거나, 문자열의 길이가 홀수이면서 다른 알파벳들은 다 짝수개 존재하고, 홀수개  존재하는 알파벳은 1개 이어야 한다.
• 위 조건이 아닌 경우, 즉 팰린드롬을 만들 수 있을 때 알파벳을 담은 str 배열을 돌면서, 해당 알파벳 갯수의 반절씩만 담고, 만약 홀수개 존재하는 알파벳이 하나 있을 때 해당 알파벳을 포함하여 ans라는 문자열을 만든다.
• ans라는 문자열을 java의 StringBuffer객체의 reverse라는 메소드를 사용해서 반대로 만든 후, ans+rever_ans 문자열을 붙여서 만든 팰린드롬 문자열을 출력해준다.

2. 문제를 풀면서 느낀점

• 처음에 DFS로 List 두 개 활용해 모든 경우를 다 돌면서 해당 조건으로 문자열을 만들도록 구현했으나 메모리 초과 났음..
• 처음 주어지는 문자열이 최대 50개라면 재귀로 완전 탐색을 하면 시간초과 이외에도, 메모리 초과가 날 수 있구나.. 명심 또 명심하자 !

 

💻 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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 s = br.readLine();
        int[] str = new int[26];
        
        int mid_Idx = 0;
        int odd = 0;
        for(int i=0;i<s.length();i++) {
        	str[s.charAt(i)-'A'] += 1;
        	
        }
        
        for(int i=0;i<str.length;i++) {
        	if(str[i]%2 == 1) {
        		mid_Idx = i;
        		odd += 1;
        	}
        }
        
        if((s.length() % 2 != 0 && odd > 1) || (s.length()%2 == 0 && odd > 0 )) {
        	bw.write(String.valueOf("I'm Sorry Hansoo"));
        } else {
        	String ans = "";
        	for(int i=0;i<str.length;i++) {
        		for(int j=0;j<str[i]/2;j++) {
        			ans += (char)(i+'A');
        		}
        	}

        	
        	String rever_ans = (new StringBuffer(ans)).reverse().toString();
        	if(odd==1) {
        		ans += (char)(mid_Idx+'A');
        	}
        	
        	bw.write(String.valueOf(ans+rever_ans));
        }
        
        bw.flush();
        bw.close();

    }


}