[SWEA 1216번] 회문2

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

SW Expert Academy

 

 

무작정 풀기

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

public class Solution {
    static int N;

    static String[][] alphabet;

    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int test = 1; test < 11; test++) {
            N = Integer.parseInt(br.readLine());
            alphabet = new String[100][100];
            result = 0;
            for (int i = 0; i < 100; i++) {
                String input = br.readLine();
                for (int j = 0; j < 100; j++) {
                    alphabet[i][j] = String.valueOf(input.charAt(j));
                }
            }

            solution();
            System.out.println("#" + N + " " + result);
        }
    }

    public static void solution() {

        // 가로
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                StringBuilder width = new StringBuilder();
                for (int k = j; k < 100; k++) {
                    width.append(alphabet[i][k]);
                    String original = width.toString();
                    String reverse = new StringBuilder(original).reverse().toString();
                    if (original.equals(reverse)) {
                        result = Math.max(result, width.length());
                    }
                }
            }
        }
        // 세로
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                StringBuilder high = new StringBuilder();
                for (int k = j; k < 100; k++) {
                    high.append(alphabet[k][i]);
                    String original = high.toString();
                    String reverse = new StringBuilder(original).reverse().toString();
                    if (original.equals(reverse)) {
                        result = Math.max(result, high.length());
                    }
                }

            }
        }
    }

}

 

DP

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

public class Solution {
    static int N;

    static String[][] alphabet;

    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int test = 1; test < 11; test++) {
            N = Integer.parseInt(br.readLine());
            alphabet = new String[100][100];
            result = 0;
            for (int i = 0; i < 100; i++) {
                String input = br.readLine();
                for (int j = 0; j < 100; j++) {
                    alphabet[i][j] = String.valueOf(input.charAt(j));
                }
            }

            solution();
            System.out.println("#" + N + " " + result);
        }
    }

    public static void solution() {

        // 가로
        for (int row = 0; row < 100; row++) {
            boolean[][] dp = new boolean[100][100];
            for (int len = 1; len < 101; len++) {
                for (int i = 0; i + len - 1 < 100; i++) {
                    int j = i + len - 1;

                    if (len == 1) {
                        dp[i][j] = true;
                    } else if (len == 2) {
                        dp[i][j] = alphabet[row][i].equals(alphabet[row][j]);
                    }else{
                        dp[i][j] = alphabet[row][i].equals(alphabet[row][j]) && dp[i+1][j-1];
                    }

                    if(dp[i][j]){
                        result=Math.max(result, len);
                    }

                }
            }
        }


        // 세로
        for(int col =0; col<100; col++){
            boolean[][] dp =new boolean[100][100];
            for(int len=1; len<101; len++){
                for(int i=0; i+len-1 < 100; i++){
                    int j = i + len -1;

                    if(len == 1){
                        dp[i][j] =true;
                    }else if(len == 2 ){
                        dp[i][j] = alphabet[i][col].equals(alphabet[j][col]);
                    }else{
                        dp[i][j] = alphabet[i][col].equals(alphabet[j][col]) && dp[i+1][j-1];
                    }

                    if(dp[i][j]){
                        result = Math.max(result, len);
                    }
                }

            }
        }
    }

}

 

 

이 문제는 시간 제한이 없어 단순하게 풀어도 되는 쉬운 문제다.
하지만 그렇게만 풀다 보면 실력 향상에 도움이 되지 않을 것 같아, DP(동적 계획법)를 활용해 보았다.
DP의 핵심은 dp[i][j]에 i번째부터 j번째까지의 ture 인지 false 인지를 저장해두는 것이다.

그리고 한 가지 참고할 점은, StringBuilder에서 reverse()를 사용하면 원본 문자열도 바뀐다는 사실을 알게 되었다...ㅎㅎ