[SWEA][JAVA] 회문2

풀이시간 : 1시간 30분

😒오래 걸린 이유

회문1과 비슷한 문제였으나 생각할 게 좀 많았다.
회문1의 경우 보드판도 작았고 회문의 길이를 정해줬었기 때문에 그만큼만 확인하면 된다.

그래서 단순하게 한 행씩 보면서 그 행에 회문의 길이만큼씩 짤라와서 회문인지 검출만 돌려봤었다.

그런데 이 문제에서 어려웠던 점은
1. 보드판이 커서 효율적으로 검출해야한다.
2. 회문의 길이가 안정해져있다.

여기서 엄청 고민을 했었다..

회문 판정

어떻게 회문을 판정해야할지 막막했다.
회문의 특성에 대해서 계속 생각하려했는데 회문은 중앙을 기준으로 좌우가 똑같다는 부분에 집착을 했다. 사실 이 부분이 생각나지 않았던게 더 도움이 되었을 거 같다.

아무튼 회문판정을 어렵게 생각했지만 그냥 단순하게 회문을 판정하면 되었다. 그 자체. 그냥 거꾸로해도 같은..그래서 reverse를 이용해서 풀이를 했다.

StringBuffer bf = new StringBuffer(str)
String reverStr = str.reverse.toString()

전체적인 사이클?

가장 어려웠던 게 사실 회문을 어떻게 할 지 알아도 이걸 어떤 식으로 돌려야할지 막막했다.

가장 단순하게는 당연히 길이를 다~해보는 것이다. 1~100까지 모~~든 길이를 탐색해서 그 중 가장 큰 회문을 확인하는..

그런데 딱 봐도 이건 아니라는 생각이 든다.
보드판이 너무 크기 때문에

그렇다면 효율적으로 탐색해야하는데 이걸 내가 아예 생각을 못했다.

우리가 구하고자하는 것은 '회문의 최대 길이'이다.
그렇기 때문에 효율적 탐색을 하려면 그냥 100부터 시작해서 -를 해나가면서 길이를 따져보면 된다..

이런 생각 자체를 못했고 이에 맞게 구현을 하는 것도 솔직히 좀 어렵게 느껴졌다.

---

💻 CODE

import java.util.*;
import java.io.*;

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

        for(int testCase = 1; testCase <=10; testCase++){
            String trash = br.readLine();
            board = new char[100][100];

            for(int i = 0 ; i < 100; i++){
                String temp = br.readLine();

                for(int j = 0 ; j < 100; j++)
                    board[i][j] = temp.charAt(j);
            }

            //만약 회문이 존재한다면 종료
            int max = 0;
            for(int findLen = 100; findLen > 0; findLen--) {
                //행
                if(findRow(findLen) == 1){
                    max = findLen;
                    break;
                }
                //열
                if(findCol(findLen) != 0){
                    max = findLen;
                    break;
                }
            }

            System.out.println("#" + testCase + " " + max);
        }
    }

    private static int findRow(int findLen) {
        //행에서 길이만큼 검출
        for(int k=0;k<100;k++){
            for(int i = 0 ; i <= 100-findLen; i++){
                //회문인지 검사하자
                String basic = "";
                for(int j = i; j < i+findLen; j++){
                    //처음 -> 끝  == 끝 -> 처음
                    basic += board[k][j];
                }
                StringBuffer bf = new StringBuffer(basic);
                String reverse = bf.reverse().toString();

                if(basic.equals(reverse)){
					return 1 ;
                }
            }
        }
        return 0;
    }

    private static int findCol(int findLen) {
        //행에서 길이만큼 검출
        for(int k=0;k<100;k++){
            for(int i = 0 ; i <= 100-findLen; i++){
                //회문인지 검사하자
                String basic = "";
                for(int j = i; j < i+findLen; j++){
                    //처음 -> 끝  == 끝 -> 처음
                    basic += board[j][k];
                }
                StringBuffer bf = new StringBuffer(basic);
                String reverse = bf.reverse().toString();

                if(basic.equals(reverse)){
					return 1 ;
                }
            }
        }
        return 0;
    }
}