[BOJ] 백준 2661 좋은수열

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

 Input 
7

 Output 

1213121

"나쁜 수열": 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있는 수열.

                 그렇지 않은 수열을 『좋은 수열』 이라고 함.

 

구현

N 길이의 모든 수열 중 주먹구구 방식으로 구한 후,

ex) N=4 일때, 1111 → 1112 → 1113 → 1121 → ... → 3333

좋은 수열 여부를 파악하기에는 시간제한.

길이 1→N 까지 좋은 수열인지 확인하며 길이 N인 수열을 만들어 갑니다. ← DFS

 

※ 코드에서 『좋은 수열』인지 판단할 때, 

    부분문자열의 길이를 {문자열 길이}/2 까지만 계산

　while(size <= str.length()/2) {...}

 

시뮬레이션

[문자열 길이 = 4]

1211 → 1자리씩 비교 ▶ 나쁜 수열

1212 → 2자리 비교 ▶ 나쁜 수열

→ 3자리씩 비교 불가

 

[문자열 길이 = 6]

123123 → 1자리씩 비교 ▶ 좋은 수열

123123 → 2자리씩 비교 ▶ 좋은 수열

123123 → 3자리씩 비교 ▶ 나쁜 수열

→ 4자리씩 비교 불가능

---

import java.util.Scanner;
 
public class Main {
    static int N;
    static boolean isEnd = false;
    static String[] available;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = Integer.parseInt(sc.next());
        DFS("1");
    }
     
    private static void DFS(String str) {
        if(isEnd) {
            return;
        }
        if(str.length() == N) {
            System.out.println(str);
            isEnd = true;
            return;
        }else {
            available = new String[] { "1", "2", "3" };
 
            for (int i = 0; i < available.length; i++) {
                // 좋은 수열을 만족하면 자릿수가 완전히 채워질때까지 계속 탐색
                if(isGoodSequence(str + available[i])) {
                    DFS(str + available[i]);
                }
            }
        }
         
    }
 
    private static boolean isGoodSequence(String str) {
        // 부분 문자열 크기
        int size = 1;
         
        // 부분의 크기가 문자열 길이만큼 되면
        // 더 이상 인접한 연속된 부분이 존재하는지 확인할 필요 없기 때문에 좋은 수열이다.
        while(size != str.length()) {
            for(int startPoint = 0; startPoint < str.length(); startPoint++) {
                // 비교한 문자열의 부분을 시작지점과 끝지점을 지정한다.
                int s1,e1,s2,e2;
                // 첫번째 부분
                s1 = startPoint; e1 = startPoint + size;
                // 두번째 부분
                s2 = e1; e2 = s2 + size;
                // 비교할 인접된 부분이 문자열 사이즈를 벗어나서는 안된다.
                if(e2 > str.length()) {
                    break;
                }
                // 나쁜 수열에 해당된다면
                if(str.substring(s1,e1).equals(str.substring(s2,e2))) {
                    return false;
                }
            }
            size++;
        }
        return true;
    }
}