[백준] 2661번: 좋은 수열 (Java)

💡문제 분석 요약

1,2,3 으로만 이루어져 있는 길이가 N인 좋은 수열 중 가장 작은 수를 구하는 문제이다.

좋은 수열은 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• 백트래킹 메서드 (`backTrack`)
  • 1, 2, 3 을 순차적으로 현재 수열(`seq`)에 추가한다.
    • `seq` 에 숫자를 추가했을 때 좋은 수열인지 검사한다. (`isGoodSeq`)
    • 좋은 수열이면 숫자를 추가하여 메서드를 재귀 호출한다.
  • `seq`의 길이가 N이 되면 출력하고 프로그램을 종료한다.
• 좋은 수열인지 검사 (`isGoodSeq`)
  • 길이가 1인 부분 수열부터 시작해서 수열의 길이 절반까지 늘려가며 검사한다. (1부터 seq.length() / 2 까지)
  • 각 길이에 대해, 마지막 i길이의 부분 수열과 바로 앞의 같은 길이의 부분 수열을 비교한다.
  • 두 부분 수열이 같으면 좋은 수열이 아니므로 false를 리턴한다.

 

💡코드

import java.io.*;

public class Main {
    static int N;

    static void backTrack(String seq) {
        if(seq.length() == N) {
            System.out.println(seq);
            System.exit(0);
        }

        for(int i=1; i<=3; i++) {
            if(isGoodSeq(seq+i))
                backTrack(seq+i);
        }
    }

    static boolean isGoodSeq(String seq) {
        int end = seq.length() / 2;
        for(int i=1; i<=end; i++) {
            String s1 = seq.substring(seq.length()-i*2, seq.length()-i);
            String s2 = seq.substring(seq.length()-i, seq.length());
            if(s1.equals(s2)) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        backTrack("");
    }
}

 

💡시간복잡도

백트래킹 메서드에서 $O(3^N)$이고, 좋은 수열인지 검사하는 메서드에서 각 수열에 대해 $O(N/2)$ 시간이 걸린다.

따라서 전체 시간복잡도는 $O(N*3^N)$이다.

 

💡 느낀점 or 기억할정보

좋은 수열인지 판별하는 코드를 생각하는데 오래걸렸다. 결국 레퍼런스를 찾아봤지만 생각보다 간단해서 아직 생각이 많이 부족하다는 느낌이 들었다ㅜ

프로그램을 종료하는 `System.exit(0)` 기억하기!