SWEA(SW Expert Academy) 1216. [S/W 문제해결 기본] 3일차 - 회문2 D3

● 문제출처

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

●정리(요약)

제대로 읽은 것과 같은 문장이나 낱말을 회문이라 한다.
100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다.

●코드 1

package swea;

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

public class Swea1216_2 {
    static char[][] board; 
    static final int SIZE = 100; 

    public static boolean hasPalindrome(int length) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col <= SIZE - length; col++) {
                if (isPalindromeInRow(row, col, length) || isPalindromeInCol(col, row, length)) {
                    return true; 
                }
            }
        }
        return false;
    }

    // 가로 방향 회문 검사
    public static boolean isPalindromeInRow(int row, int startCol, int length) {
        for (int offset = 0; offset < length / 2; offset++) {
            if (board[row][startCol + offset] != board[row][startCol + length - 1 - offset]) {
                return false; 
            }
        }
        return true;
    }

    // 세로 방향 회문 검사
    public static boolean isPalindromeInCol(int startRow, int col, int length) {
        for (int offset = 0; offset < length / 2; offset++) {
            if (board[startRow + offset][col] != board[startRow + length - 1 - offset][col]) {
                return false; 
            }
        }
        return true; 
    }

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

        for (int testCase = 0; testCase < 10; testCase++) {
            int t = Integer.parseInt(br.readLine()); 
            board = new char[SIZE][SIZE]; 


            for (int row = 0; row < SIZE; row++) {
                String line = br.readLine();
                for (int col = 0; col < SIZE; col++) {
                    board[row][col] = line.charAt(col);
                }
            }

           
            for (int length = SIZE; length > 0; length--) {
                if (hasPalindrome(length)) {
                    System.out.println("#" + t + " " + length);
                    break; 
                }
            }
        }
        br.close(); 
    }
}

● 코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Solution
{
    static String[] arr;
    static long max;
    static StringBuilder sb= new StringBuilder();
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        for(int i=1; i<=10; i++) {
            int T = Integer.parseInt(br.readLine());
             
            arr = new String[100];
            max = 1;
             
            //가로
            for(int j=0; j<100; j++) {
                String str = br.readLine();
                arr[j]=str;
                palindrome(str, 100);
            }
             
            for(int j =0; j<100; j++) {
                String ing = "";
                for(int k=0;k<arr.length;k++) {
                    ing += arr[k].charAt(j);
                }
                palindrome(ing,100);
            }
             
            System.out.println("#"+T+" "+max);
        }
         
    }
     
    public static void palindrome(String str ,int length) {
        int st = 0;
        String tmp1 = "";
        String tmp2 = "";
        while(length>1||length>max) {
            tmp1 = str.substring(st,st+length);
            StringBuffer sb = new StringBuffer(tmp1);
            tmp2 = sb.reverse().toString();
             
            if(tmp1.equals(tmp2)) {
                max = Math.max(max, length);
                break;
            }
             
            st++;
            if(st+length>100) {
                st=0;
                length--;   
            }
        }
         
    }
 
}

● 느낀점
회문 1 문제 처럼 코드2는 StringBuffer를 사용해 .reverse() 썻고 코드1은 세로 가로 검사하면서 먼저 나오는 것을 return하여 최대길이를 출력하였다. (참고로 코드1은 String ing에 넣는것이 비효율적이지만 푸는데 문제없어서 그냥 진행하였다.)