[SWEA] 1215. [S/W 문제해결 기본] 3일차 - 회문1 (D3) - java

문제

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

SW Expert Academy

 

접근법

회문의 길이가 정해져있기 때문에 각 위치에서 정해진 길이만큼을 회문인지 아닌지 판단하면 된다. 나는 입력을 2차원 배열로 저장했고, (0, 0)부터 시작한다면 오른쪽(가로 문자열), 아래(세로 문자열)만 확인하면 되기 때문에 이를 참고해서 반복문을 작성했다.

 

매번 (r, c)에서 회문의 길이만큼 문자열을 만들어서 회문인지 아닌지 판단하는 것은 중복되는 연산이 많이 생길 것이라고 생각해서 슬라이딩 윈도우 개념을 사용해 풀어보았다.

 

 

여기서 생각할 점은 (0, 0)에서 시작했을 때 재귀함수와 슬라이딩 윈도우를 사용해 위 사진처럼 회문인지 검사를 했다면, 0행에 있는 모든 문자열은 이미 검사를 진행했으므로 다음 행으로 넘어가야 한다.

즉, 가로 문자열로 생각했을 때 (0, 0), (1, 0), (2, 0)... 각 행에서 시작한다면 재귀함수로 인해 알아서 같은 줄의 맨 끝까지 검사하게 되는 것이다. 세로 문자열의 경우도 (0, 0), (0, 1), (0, 2)... 에서 세로 문자열을 확인하도록 재귀함수를 시작한다면 맨 끝까지 검사하게 된다. 따라서 반복문의 범위를 잘 설정해야 한다 

 

for (int i = 1; i < 8; i++) {
	s1 = s2 = "";

	for (int j = 0; j < length; j++) {
    	s1 += board[j][i];
     	s2 += board[i][j];
	}
    
    dfs(new Point(length - 1, i), s1, 0);
    dfs(new Point(i, length - 1), s2, 1);
}

나는 이렇게 각 시작점만 계산해서 재귀함수로 넘겨주도록 작성하였다. i가 1부터 시작하는 이유는 0부터 시작할 경우 0에서 가로 세로 문자열을 검사하는 것이 중복되기 때문에 따로 빼서 계산했다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static char[][] board;
    static int length; // 회문의 길이
    static List<String> palindrome;

    // 0: 세로 / 1: 가로
    static int[] dirR = {1, 0};
    static int[] dirC = {0, 1};

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

        for (int t = 1; t <= 10; t++) {
            board = new char[8][8];
            length = Integer.parseInt(br.readLine());
            palindrome = new ArrayList<>();

            for (int r = 0; r < 8; r++) {
                String s = br.readLine();
                for (int c = 0; c < 8; c++) {
                    board[r][c] = s.charAt(c);
                }
            }

            // (0, 0)은 따로 계산
            String s1 = ""; // 세로
            String s2 = ""; // 가로
            for (int i = 0; i < length; i++) {
                s1 += board[i][0];
                s2 += board[0][i];
            }
            dfs(new Point(length - 1, 0), s1, 0);
            dfs(new Point(0, length - 1), s2, 1);

            // 나머지
            for (int i = 1; i < 8; i++) {
                s1 = s2 = "";

                for (int j = 0; j < length; j++) {
                    s1 += board[j][i];
                    s2 += board[i][j];
                }

                dfs(new Point(length - 1, i), s1, 0);
                dfs(new Point(i, length - 1), s2, 1);
            }

            sb.append('#').append(t).append(' ').append(palindrome.size()).append('\n');
        }

        System.out.println(sb);
    }

    private static void dfs(Point end, String s, int d) {
        if (isPalindrome(s)) {
            palindrome.add(s);
        }

        // 문장 끝나는 지점 이동
        end.move(d);
        if (!rangeIn(end)) {
            return;
        }

        // 새로운 문장 만들기
        s = s.substring(1) + board[end.r][end.c];
        dfs(end, s, d);
    }

    private static boolean rangeIn(Point p) {
        return (p.r >= 0) && (p.c >= 0) && (p.r < 8) && (p.c < 8);
    }

    private static boolean isPalindrome(String s) {
        boolean palindrome = true;
        int start = 0;
        int end = s.length() - 1;

        while (start <= end) {
            if (s.charAt(start) != s.charAt(end)) {
                palindrome = false;
                break;
            }

            start++;
            end--;
        }


        return palindrome;
    }

    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }

        private void move(int direction) {
            this.r += dirR[direction];
            this.c += dirC[direction];
        }
    }

}

 

주의할 점

반복문의 범위를 어떻게 설정해야 할지 감이 안 잡힐 때, 그림으로 원하는 반복문의 형태를 그려보고 좌표만 찍어보는 반복문을 사용해서 틀을 잡고 코드를 짜자!