[Java] SWEA 4672번 수진이의 팰린드롬

SW Expert Academy

---

풀이

 

문제 예시에서 세 번째 테스트 케이스를 abccba로 바꾸면 팰린드롬인 부분 문자열의 개수가 최대인데 이때의 부분 문자열 중 팰린드롬인 것은 a, a, b, b, c, c, aa, bb, cc이고 이는 aabbcc인 문자열의 연속한 부분을 뽑아 만든 부분 문자열이 됩니다.

이를 이용해서 입력받은 문자열을 사전 순으로 정렬하기 위해 한 글자씩 잘라 배열을 만들고 배열을 정렬한 후 다시 문자열로 합쳐주었습니다.

그다음으로 부분집합을 만들어 연속된 일부분을 뽑아 만든 부분 문자열을 만들고 그 부분 문자열이 팰린드롬이라면 팰린드롬의 개수를 증가시켜 해결했습니다.

---

코드

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

public class Solution {
	public static int answer;
	public static String input_s, str;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");

		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			input_s = br.readLine();
			
			// 한 글자씩 자른다
			String[] arr = input_s.split("");
			Arrays.sort(arr);
			str = String.join("", arr);
			
			answer = 0;
			for (int i = 0; i < str.length(); ++i) {
				powerset(Character.toString(str.charAt(i)), i + 1);
			}
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static void powerset(String s, int idx) {
		isPalindrome(s);
		
		if (idx == str.length()) {
			return;
		}
		
		powerset(s + Character.toString(str.charAt(idx)), idx + 1);
	}
	
	public static void isPalindrome(String s) {
		int start = 0;
		int end = s.length() - 1;
		
		while (start < end) {
			if (s.charAt(start) != s.charAt(end)) {
				return;
			}
			
			start++;
			end--;
		}
		
		answer++;
	}
}

---

pyo7410/Algorithm