[SW Expert Academy/Java/D3] 1216.회문2

1) SW Expert Academy 정책상 문제 자체를 퍼가는 것은 금지되며 링크와 출처로 명시해 주시기 바랍니다.
2) 문제에 대한 본인의 풀이에 대해서는 개인 학습 등 상업적 용도가 아닌 경우에만 문제 출처와 함께 게시가 가능합니다.
    
※ 저작권 이슈가 있을 시 법적 제재를 받을 수 있으니 참고하여주시기 바랍니다.

 

문제 설명

SW Expert Academy

 

나의 풀이

import java.util.Scanner;

class Solution {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = 10;  // 테스트 케이스 수

        for (int t = 1; t <= T; t++) {
            int testCase = sc.nextInt(); // 테스트 케이스 번호
            String[][] map = new String[100][100];

            // 100줄 입력받아서 문자 하나씩 2차원 배열에 저장
            for (int i = 0; i < 100; i++) {
                String line = sc.next(); // 한 줄 입력 (길이 100짜리 문자열)
                for (int j = 0; j < 100; j++) {
                    map[i][j] = String.valueOf(line.charAt(j));
                }
            }

            int answer = 0;

            // ==================================
            // [1] 가로 회문 검사
            // ==================================
            for (int row = 0; row < 100; row++) {
                for (int start = 0; start < 100; start++) {
                    StringBuilder sb = new StringBuilder();
                    for (int end = start; end < 100; end++) {
                        sb.append(map[row][end]); // start ~ end까지 문자열 구성
                        String str = sb.toString();
                        String reversed = new StringBuilder(str).reverse().toString();
                        if (str.equals(reversed)) {
                            if (str.length() > answer) {
                                answer = str.length(); // 최대 회문 길이 갱신
                            }
                        }
                    }
                }
            }

            // ==================================
            // [2] 세로 회문 검사
            // ==================================
            for (int col = 0; col < 100; col++) {
                for (int start = 0; start < 100; start++) {
                    StringBuilder sb = new StringBuilder();
                    for (int end = start; end < 100; end++) {
                        sb.append(map[end][col]); // start ~ end까지 세로 문자열 구성
                        String str = sb.toString();
                        String reversed = new StringBuilder(str).reverse().toString();
                        if (str.equals(reversed)) {
                            if (str.length() > answer) {
                                answer = str.length(); // 최대 회문 길이 갱신
                            }
                        }
                    }
                }
            }

            // 출력
            System.out.println("#" + testCase + " " + answer);
        }
    }
}

 

개선된 코드

import java.util.Scanner;

class Solution {
	// 회문인지 검사하는 함수 (char 배열과 시작 인덱스, 길이, 방향)
    static boolean isPalindrome(char[][] map, int x, int y, int len, boolean isRow) {
        for (int i = 0; i < len / 2; i++) {
            // 방향에 따라 검사 위치가 달라짐
            char a = isRow ? map[x][y + i] : map[y + i][x];
            char b = isRow ? map[x][y + len - 1 - i] : map[y + len - 1 - i][x];
            if (a != b) return false; // 한 쌍이라도 다르면 회문 아님
        }
        return true; // 모든 쌍이 같다면 회문임
    }

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = 10; // 문제에서 고정된 테스트케이스 개수

        // 각 테스트케이스 반복
        for (int t = 1; t <= T; t++) {
            int testCase = sc.nextInt(); // 테스트케이스 번호 (출력용)
            char[][] map = new char[100][100]; // 100x100 크기의 문자 배열 선언

            // 입력: 각 줄을 문자열로 받아서 문자 배열로 변환하여 map에 저장
            for (int i = 0; i < 100; i++) {
                String line = sc.next(); // 길이 100짜리 문자열
                map[i] = line.toCharArray(); // 문자열을 문자 배열로 변환해 한 줄 저장
            }

            int answer = 0; // 최종 정답 (가장 긴 회문의 길이)

            // 회문의 길이를 100부터 1까지 줄여가며 탐색
            // 긴 회문을 먼저 찾으면 바로 종료 가능 → 성능 최적화
            for (int len = 100; len >= 1; len--) {
                boolean found = false; // 해당 길이의 회문이 발견되면 true

                // [1] 행 검사 (가로 방향)
                for (int row = 0; row < 100 && !found; row++) { // 모든 행 순회
                    for (int start = 0; start <= 100 - len; start++) { // 해당 행의 가능한 시작 위치 순회
                        if (isPalindrome(map, row, start, len, true)) {
                            answer = len; // 최대 회문 길이 갱신
                            found = true; // 찾았으므로 더 이상 이 길이 이하를 검사할 필요 없음
                            break;
                        }
                    }
                }

                // [2] 열 검사 (세로 방향)
                for (int col = 0; col < 100 && !found; col++) { // 모든 열 순회
                    for (int start = 0; start <= 100 - len; start++) { // 해당 열의 가능한 시작 위치 순회
                        if (isPalindrome(map, col, start, len, false)) {
                            answer = len;
                            found = true;
                            break;
                        }
                    }
                }

                if (found) break; // 현재 회문 길이에서 발견되었으므로 루프 종료
            }

            // 정답 출력
            System.out.println("#" + testCase + " " + answer);
        }
    }
}

 

StringBuilder 사용 풀이

import java.util.Scanner;

class Solution {

    static boolean isPalindrome(char[][] map, int x, int start, int len, boolean isRow) {
        StringBuilder sb = new StringBuilder();

        // 문자열 만들기
        for (int i = 0; i < len; i++) {
            // 행 검사일 경우 → 같은 행, start부터 오른쪽으로
            // 열 검사일 경우 → 같은 열, start부터 아래로
            if (isRow) {
                sb.append(map[x][start + i]);
            } else {
                sb.append(map[start + i][x]);
            }
        }

        // 문자열을 뒤집은 결과와 원본이 같으면 회문
        String str = sb.toString();
        String reversed = sb.reverse().toString();
        return str.equals(reversed);
    }

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = 10; // 총 테스트 케이스 수

        for (int t = 1; t <= T; t++) {
            int testCase = sc.nextInt(); // 테스트케이스 번호 입력
            char[][] map = new char[100][100]; // 100x100 크기의 문자 배열

            // 100줄 입력받기 → 한 줄씩 char 배열로 저장
            for (int i = 0; i < 100; i++) {
                String line = sc.next();
                map[i] = line.toCharArray();
            }

            int answer = 0; // 가장 긴 회문의 길이를 저장

            // 회문 길이를 100부터 1까지 줄여가며 검사
            for (int len = 100; len >= 1; len--) {
                boolean found = false;

                // 행 검사
                for (int row = 0; row < 100 && !found; row++) {
                    for (int start = 0; start <= 100 - len; start++) {
                        if (isPalindrome(map, row, start, len, true)) {
                            answer = len;
                            found = true;
                            break;
                        }
                    }
                }

                // 열 검사
                for (int col = 0; col < 100 && !found; col++) {
                    for (int start = 0; start <= 100 - len; start++) {
                        if (isPalindrome(map, col, start, len, false)) {
                            answer = len;
                            found = true;
                            break;
                        }
                    }
                }

                if (found) break; // 가장 긴 회문을 찾았으면 더 짧은 건 검사할 필요 없음
            }

            // 출력
            System.out.println("#" + testCase + " " + answer);
        }
    }
}