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

[1216] 회문 2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14Rq5aABUCFAYi

• 지정된 길이의 회문 개수를 찾는 회문 1 에서 이어지는 문제
• 주어진 100X100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다.

 

 

Solution

• 회문 len = 2 ~ 100 까지의 모든 경우를 탐색하는 풀이 방법

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int T, n, m, answer;
    static String[][] map;
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            T = stoi(br.readLine());
            init();
            for (int i = 0; i < 100; i++) {
                map[i] = br.readLine().split("");
                solve(map[i]);
            }
 
            String[] temp;
            for (int i = 0; i < 100; i++) {
                temp = new String[100];
                for (int j = 0; j < 100; j++) {
                    temp[j] = map[j][i];
                }
                solve(temp);
            }
 
            System.out.println("#" + T + " " + answer);
 
            if (T == 10) {
                break;
            }
        }
 
    }
 
    static void solve(String[] arr) {
        int len = 100;
        while (len-- > 0) {
            StringBuilder sb;
         A:    for (int i = 0; i <= arr.length - len; i++) {
                sb = new StringBuilder();
                for (int j = i; j < i + len; j++) {
                    sb.append(arr[j]);
                }
                if (isPalindrome(sb.toString(), len)) {
                    answer = Math.max(answer, len);
                    break A;
                }
            }
        }
    }
 
    static boolean isPalindrome(String word, int len) {
        String front = word.substring(0, len / 2);
        String back;
        if (len % 2 == 0)
            back = word.substring(len / 2, len);
        else
            back = word.substring(len / 2 + 1, len);
 
        for (int i = 0; i < len / 2; i++) {
            if (front.charAt(i) != back.charAt(len / 2 - i - 1))
                return false;
        }
        return true;
    }
 
    static void init() {
        answer = 1;
        map = new String[100][100];
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
 
    static void print(String[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
}