[S/W 문제해결 기본] 3일차 - 회문2 (D3)

문제 링크

• 회문2는 100*100 배열에서 회문 단어를 찾는 문제이다.
• 회문1에서는 타겟 단어의 길이가 주어지지만 회문2는 찾을 수 있는 가장 큰 회문의 길이를 찾는 문제이다.
• 따라서 각 행/열에서 100부터 -1 씩 글자수를 줄여 회문단어를 탐색하고 해당 단어가 회문이면 max값을 갱신하고 굳이 max보다 작은 글자수의 회문을 확인하지 않아도 된다.

Solution

package swea;

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

// [S/W 문제해결 기본] 3일차 - 회문2
public class p1216 {
	public static boolean palindrome(StringBuffer sb) {
		String str1 = sb.toString();
		String str2 = sb.reverse().toString();
		sb.reverse();
		if (str1.equals(str2))
			return true;
		return false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int t = 1; t <= 10; t++) {
			br.readLine();
			StringBuffer[] colSb = new StringBuffer[100];
			for (int i = 0; i < 100; i++) {
				colSb[i] = new StringBuffer();
			}
			StringBuffer sb;

			int max = 0;
			for (int i = 0; i < 100; i++) { // 한줄 입력받고, 가로 확인
				String inputLine = br.readLine();

				for (int j = 0; j < 100; j++) { // 세로 확인용 sb에 저장
					colSb[j].append(inputLine.charAt(j));
				}

				check: for (int j = 100; j > max; j--) { // 체크할 글자수
					for (int k = 0; k <= 100 - j; k++) { // 글자수로 한줄에 몇번 체크할지 계산
						sb = new StringBuffer(inputLine.substring(k, k + j));
						if (palindrome(sb)) {
							max = j;
							break check; // 100부터 -- 했으니까 max찾으면 끝
						}
					}
				}
			} // 가로 for

			for (int i = 0; i < 100; i++) { // 세로 확인
				String colLine = colSb[i].toString();
				check: for (int j = 100; j > max; j--) { // 체크할 글자수
					for (int k = 0; k <= 100 - j; k++) { // 글자수로 한줄에 몇번 체크할지 계산
						sb = new StringBuffer(colLine.substring(k, k + j));
						if (palindrome(sb)) {
							max = Math.max(max, j);
							break check; // 100부터 -- 했으니까 max찾으면 끝
						}
					}
				}
			}
			System.out.printf("#%d %d\n", t, max);
		}

	}
}