백준 2661 좋은수열 Java

알고리즘 분류 백트래킹으로 분류되어있는 좋은 수열 문제이다.

 

내가 헷갈렸던 부분은

수열을 인접한 두 개의 부분 수열을 검사하는 부분이었다.

 

생각의 폭이 좁아서인지 검사를 앞에서부터 해야 한다고 생각했다.

그래서 방법을 떠올리기가 힘들었다.

하지만 검사할 때 뒤에서부터, 새로 추가된 수부터 검사를 하면

되는 것이었다.

 

새로 1, 2, 3 중 하나의 수를 추가할 때 앞에 수랑 겹치지 않게 추가하고

뒤에서부터 2개씩, 3개씩.. n/2개씩 검사하면 되는 문제였다.

 

String클래스의 substring메소드를 활용해서 검사했는데

처음엔 무조건 2개씩 검사하므로 k라는 변수에 2를 넣고 substring으로

범위를 설정해서 검사하였고 k를 1씩 늘렸다.

 

검사는 무조건 길이/2까지 하기 때문에

k가 문자열의 길이/2보다 커지면 반복문을 종료하면 된다.

다만 이렇게 검사하면 길이가 4보다 작은 문자열은 k가 2부터 시작하기 때문에

substring호출 시에 에러가 발생하므로 조건을 설정해줘야 한다.

길이가 4보다 작은 문자열은 바로 앞에 수와 겹치지 않게 수를 넣어주므로

무조건 좋은 수열이 나오게 된다.

 

또한 이렇게 호출을 하면서 맨 처음 발견된 길이가 n인 문자열이 가장 작은 좋은 수열이므로

n인 문자열을 처음 찾았을 때 그 문자열을 출력하고 나머지 호출들을 정리시키기 위해

System.exit(0)으로 프로그램을 종료시켰다.

boolean형 변수를 하나 둬서 다른 호출들을 전부 return 시키는 방법도 있다.

 

import java.util.Scanner;
 
public class Q2661 {
    public static int n;
    
    public static boolean isCheck(String s) {
        int len = s.length();
        int k = 2;
        while(k <= len/2) {
            if(s.substring(len-k, len).equals(s.substring(len-(2*k), len-k))){
                return false;
            }
            k++;
        }
        return true;
    }
    
    public static void backtrack(String s) {
        if(s.length() == n) {
            System.out.println(s);
            System.exit(0);
        }
        for(int i=1; i<=3; i++) {
            if(s.charAt(s.length()-1)-'0' == i) continue;
            if(s.length()+1 < 4) {
                backtrack(s+i);
            }else if(isCheck(s+i)) {
                backtrack(s+i);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        backtrack("1");
        
    }
}