[JAVA][SW Expert Academy] 1215. 회문2

 

 [SW Expert Academy] 1215. 회문2

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi&categoryId=AV14QpAaAAwCFAYi&categoryType=CODE

SW Expert Academy

---

 문제 내용

"기러기" 또는 "level" 과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다. 주어진 100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다. 위와 같은 글자 판이 주어졌을 때, 길이가 가장 긴 회문은 붉은색 테두리로 표시된 7칸짜리 회문이다. 예시의 경우 설명을 위해 글자판의 크기가 100 x 100이 아닌 8 x 8으로 주어졌음에 주의한다. [제약사항] 각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다. 글자 판은 무조건 정사각형으로 주어진다. ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다. 가로, 세로 각각에 대해서 직선으로만 판단한다. 즉, 아래 예에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.    [입력] 각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트케이스가 주어진다. [출력] #부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 길이를 출력한다.

 

 해결 순서

1. 1214. 회문1 문제의 응용 케이스 (https://minz-sw.tistory.com/13)
2. 행/열 최대 100회 반복하며 내림차순으로 회문 찾기
3. 행/열 내에서 최대 회문 길이에 따라 n(<=100)번 반복 필요

 - 배열 값 비교 또는 StringBuffer 사용 가능

 

 

 문제 풀이 - 배열

import java.util.Scanner;
 
public class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = 10;
        
        for(int test_case = 1; test_case <= T; test_case++)
        {
            String TC = sc.next();
            String s_tc = sc.next();
            String[][] arr_s = new String[100][100];
            
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    arr_s[j][i] = s_tc.substring(j, j+1);
                }
                if (i < s_tc.length()-1) {
                    s_tc = sc.next();
                }
            }
            for (int maxLen = 100; maxLen > 0; maxLen--) {
                if (find(arr_s, maxLen)) {
                    System.out.println("#" + test_case + " " + maxLen);
                    break;
                }
            }
        }
    }
    
    public static boolean find(String[][] arr_s, int maxLen) {
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <= 100 - maxLen; j++) {
                if (findX(arr_s, i, j, maxLen) | findY(arr_s, i, j, maxLen)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public static boolean findX(String[][] arr_s, int i, int j, int maxLen) {
        for (int k = 0; k < maxLen / 2; k++) {
            if (!arr_s[i][j+k].equals(arr_s[i][j-(k+1)+maxLen])) {
                return false;
            } 
        }
        return true;
    }
 
    public static boolean findY(String[][] arr_s, int i, int j, int maxLen) {
        for (int k = 0; k < maxLen / 2; k++) {
            if (!arr_s[j+k][i].equals(arr_s[j-(k+1)+maxLen][i])) {
                return false;
            } 
        }
        return true;
    }
}

 

 

 문제 풀이 - StringBuffer.reverse

import java.util.Scanner;
 
public class Solution2
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = 10;
        
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int TC = sc.nextInt();
            String s_tc = sc.next();
            String[][] arr_s = new String[100][100];
            
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    arr_s[j][i] = s_tc.substring(j, j+1);
                }
                if (i < 99) {
                    s_tc = sc.next();
                }
            }
            
            for (int maxLen = 100; maxLen > 0; maxLen--) {
                if (find(arr_s, maxLen)) {
                    System.out.println("#" + test_case + " " + maxLen);
                    break;
                }
            }
            
        }
    }
    
    public static boolean find(String[][] arr_s, int maxLen) {
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <= 100 - maxLen; j++) {
                if (findX(arr_s, i, j, maxLen) | findY(arr_s, i, j, maxLen)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public static boolean findX(String[][] arr_s, int i, int j, int maxLen) {
        String s = "";
        int count = 0;
        
        while (count < maxLen) {
            s += arr_s[i][j+count];
            count++;
        }
        
        StringBuffer bf = new StringBuffer(s);
        String rev_s = bf.reverse().toString();
        
        if (s.equals(rev_s)) {
            return true;
        } else {
            return false;
        }
    }
 
    public static boolean findY(String[][] arr_s, int i, int j, int maxLen) {
        String s = "";
        int count = 0;
        
        while (count < maxLen) {
            s += arr_s[j+count][i];
            count++;
        }
        
        StringBuffer bf = new StringBuffer(s);
        String rev_s = bf.reverse().toString();
        
        if (s.equals(rev_s)) {
            return true;
        } else {
            return false;
        }
    }
}

 

 

 참고

[배열 비교]

[StringBuffer reverse]

StringBuffer의 reverse를 사용하면 엄청나게 오래걸린다...