[Java] 백준 2661 좋은수열

https://www.acmicpc.net/problem/2661

난이도

골드 4

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123
  길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

내 코드

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

class Main {

    static int N;
    static boolean found = false; 
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        dfs("");
        
    }

    public static void dfs(String str){
        if(found) return;
        
        if (str.length() == N) {
            System.out.println(str);
            found = true;
            return;
        }

        for (int i = 1; i <= 3; i++){
            String next = str + i;
            if (isGood(next)) {
                dfs(next);
            }
        }
    }

    public static boolean isGood(String s){
        int len = s.length();

        for (int i = 1; i <= len / 2; i++) {
            String left = s.substring(len - i * 2, len - i);
            String right = s.substring(len - i);
            if (left.equals(right)) return false;
        }
        return true;
    }
}

isGood() 함수 설명

for (int i = 1; i <= len / 2; i++) {
    String left = s.substring(len - i * 2, len - i);
    String right = s.substring(len - i);
    if (left.equals(right)) return false;
}

반복문의 의미

for (int i = 1; i <= len / 2; i++)

• 길이가 2 * i인 마지막 두 부분 수열을 비교

• 예시:

  • i = 1 → 마지막 1칸씩 비교
  • i = 2 → 마지막 2칸씩 비교
  • ...

• 뒤에서부터 점점 길이를 늘려가며 중복되는 인접 부분 수열이 있는지 확인

부분 문자열 추출

String left = s.substring(len - i * 2, len - i);
String right = s.substring(len - i);

변수	설명
len	현재 문자열 s의 전체 길이
len - i * 2	앞쪽 수열의 시작 인덱스
len - i	앞쪽 수열의 끝 인덱스 (exclusive) 동시에 뒤쪽 수열의 시작 인덱스
len	뒤쪽 수열의 끝 인덱스 (exclusive)

수열 비교 조건

if (left.equals(right)) return false;

• left와 right가 같다면 → 나쁜 수열
• 인접한 두 부분 수열이 중복되므로 즉시 false 반환