[JAVA/자바][백준 1802] 종이 접기

문제

---

1802번: 종이 접기

1802번: 종이 접기

 

 

접근 방법

---

분할 정복 문제 모음집을 따라 풀던 중 만난 문제다. 인덱스를 잘 구분하면 쉬운 문제다.

• 중간 값은 어느 방향으로 접어도 상관이 없다.
  • 문자열의 길이 = 1 일 경우도 마찬가지
• 중간값을 기준으로 대칭되는 좌, 우의 값이 달라야 한다.
  • 접었을 때 포개지는 곳은 다음 차례에 각각 서로 다른 방향으로 접히게 된다.
• 재귀 함수를 이용한다.

 

 

풀이

---

1. 규칙을 만족하는지 판단하는 boolean 함수 check 선언
   • 인자 : 문자열의 시작 인덱스, 마지막 인덱스
2. 문자열의 길이가 1(문자열의 시작 = 문자열의 끝)일 때 true를 반환한다.
   • 재귀 함수에서의 탈출 조건이 된다.
3. 중간 값을 기준으로 대칭되는 좌, 우 쌍을 비교한다.
4. (시작 인덱스 ~ 중간 인덱스-1)와 (중간 인덱스+1 ~ 마지막 인덱스)의 범위를 재귀함수로 실행한다.
5. (2 ~ 4) 과정을 반복한다.

 

 

코드

---

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

public class Main {
    private static String input;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            input = br.readLine();
            if (check(0, input.length() - 1)) {
                sb.append("YES").append("\n");
            } else {
                sb.append("NO").append("\n");
            }
        }
        System.out.println(sb);
    }

    private static boolean check(int start, int end) {
        if (start == end) {
            return true;
        }
        int mid = (start + end) / 2;
        for (int i = start; i < mid; i++) {
            if (input.charAt(i) == input.charAt(end - i)) {
                return false;
            }
        }
        return check(start, mid - 1) && check(mid + 1, end);
    }
}