1213번 - 팰린드롬 만들기

 

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

1213번: 팰린드롬 만들기

 

 

 

 

 

순열을 구해 모든 경우의 수에 대해 팰린드롬인지 판별해줬다.

근데 시간초과가 났다... 생각해보니 50글자면 무려 50!이나 된다.

 

 

 

 

 

코드 - 시간 초과

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class b1213 {
	static char[] chs;
	static boolean[] visited;
	static char[] result;
	static List<String> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		chs = sc.next().toCharArray();
		
		visited = new boolean[chs.length];
		result = new char[chs.length];
		list = new ArrayList<>();
		
		permutation(0); //순열
		
		//출력
		if(list.size() == 0) {
			System.out.println("I'm Sorry Hansoo");
		} else {
			Collections.sort(list);
			System.out.println(list.get(0));
		}
	}

	public static void permutation(int count) {
		if(count == chs.length) {
			if(isPalindrome()) { //팰린드롬 판별
				String str = String.valueOf(result);
				list.add(str);
			}
			
			return;
		}
		
		for(int i = 0; i < chs.length; i++) {
			if(visited[i]) continue;
			visited[i] = true;
			
			result[count] = chs[i]; //결과 배열에 저장
			
			permutation(count + 1);
			visited[i] = false;
		}
		
	}

	public static boolean isPalindrome() {
		for(int i = 0; i < chs.length / 2; i++) {
			if(result[i] != result[chs.length - i - 1]) {
				return false;
			}
		}
		return true;
	}

}

 

 

 

 

 

 

시간을 줄이기 위해서 먼저 팰린드롬이 안되는 경우의 수를 걸러줘야 한다.

 

어떤 알파벳 수가 홀수개인 것이 2개 이상이면, 팰린드롬이 될 수가 없다. 0개 또는 1개(해당 알파벳이 가운데에 들어감)여야 한다. 

그래서 순열에 앞서 각 알파벳 수를 카운팅하고 홀수개인 것이 2개인지 판별해주는 것을 추가해줬다.

 

그러나 시간초과... 그래도 순열을 사용해서 여전히 많은 시간이 걸린다.

순열을 버리고 직접 팰린드롬인 문자를 만들어줘야 한다는 접근을 듣고 그렇게 풀었다.

 

 

 

 

 

코드 - 성공

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String input = sc.next();
		
		int[] alphabet = new int[26];
		
		for(int i = 0; i < input.length(); i++) { //알파벳 수 저장
			alphabet[input.charAt(i) - 'A']++;
		}
		
		int oddCount = 0;
		char oddChar = ' ';
		for(int i = 0; i < 26; i++) { //홀수개인 알파벳 개수 세기
			if(alphabet[i] % 2 == 1) {
				oddCount++;
				oddChar = (char)(i + 65);
			}
			
			if(oddCount == 2) break;
		}
		
		String answer = "";
		if(oddCount == 2) { //불가능
			answer = "I'm Sorry Hansoo";
		} else { //홀수개인 알파벳 0개 or 1개
			String front = "";
			String tail = "";
			
			for(int i = 0; i < 26; i++) {
				if(alphabet[i] >= 2) {
					for(int j = 0; j < alphabet[i] / 2; j++) {
						front += (char)(i + 65);
					}
				}
			}
			
			StringBuilder sb = new StringBuilder(front);
			tail = sb.reverse().toString();
			
			if(oddCount == 0) { //정답 도출
				answer = front + tail;
			}else if(oddCount == 1){
				answer = front + oddChar + tail;
			}
		}
		
		//출력
		System.out.println(answer);
	}

}

 

 

 

 

 

각각의 알파벳이 나오는 수를 저장하는 26칸 짜리 배열을 만든다. 그리고 홀수개인 알파벳 개수를 센다.

이때 형변환에 주의해줘야 한다. 대문자 A의 아스키 코드인 65를 기억해줘야 한다.

 

홀수개인 알파벳 개수를 세면서 해당 문자를 저장하도록 했다. 그리고  2개 이상이면 그만두게 했다.

 

그 다음 2개면 불가능하다고 하고, 0개나 1개이면 팰린드롬 문자열을 만들도록 했다.

사전순으로 했을 때 가장 먼저오는 팰린드롬을 출력해야 하므로, 알파벳 순서대로 탐색을 해 문자열을 만들도록 했다.

팰린드롬은 대칭이므로 앞 중간 뒤로 나눴다. 알파벳을 절반으로 나눠서 순서대로 하나씩 문자를 붙여 앞 문자열을 만들었다. 그리고 String의 reverse() 메소드를 이용하여 앞 문자열을 뒤집어서 뒤 문자열을 만들었다. reverse를 하려면 StringBuilder StringBuilder로 변환해줘야 한다.

 

그리고 0개이면 중간 문자열 없이 앞뒤만 붙여서 정답을 도출하고, 1개인 경우에는 중간에 홀수개인 알파벳을 붙여줬다.

 

 

 

 

 

결과