문제 탐색하기

입력 자료 정리

1. N은 문자열의 최대 길이로, 백트래킹의 base condition 조건이 된다

해결방법 추론

1. 1,2,3중 하나를 선택하는 백트래킹을 하면 된다고 생각했다
2. 단 좋은 수열을 만족시킬 때, 백트래킹을 진행한다
3. 좋은 수열을 검증하는 로직과 백트래킹으로 해결할 수 있을 것이라고 생각했는데...
   문제는 최대 입력이 80이라 시간초과나 메모리 초과가 발생할 것으로 보인다
4. 다행히 이 문제를 해결하여 풀 수 있도록 가장 작은 수만 출력하도록 하였다
5. 가장 작은 수는 맨 처음 base condition에 도달하는 경우다.
6. 따라서 이때 문자열을 출력하고 System.exit(0)으로 아예 종료시켜버리면
   문제없이 해결할 수 있을 것이라 생각하였다

시간복잡도 계산

1. 따라서 시간복잡도는 최대 80번의 연산과 문자열의 절반 길이까지 탐색하여 검증하기 때문에 40의 연산이 발생하여 O(80 x 40)의 시간복잡도가 발생할 것이다

코드 설계하기

입력값 상태 관리

1. 입력값 n은 변수로 관리하였다

백트래킹 설계

1. 백트래킹은 단순하게 설계한다 입력값 n과 문자열 s를 파라미터로 갖는다
2. 1부터 3까지 순회하면서 좋은 조건 검증 메소드에 기존 문자열과 현재 숫자를 더해 넘기고,
   만약 조건을 만족한다면 백트래킹에 똑같이 인수로 넘겨준다
3. 이렇게 base condition에 도달하였을 때, 처음 도달한 값이 가장 작은 수가 된다
4. 그 이후에 수를 더 받게 되면 시간초과나 메모리초과가 발생하므로,
   여기서 그냥 문자열을 출력하고 System.exit(0);으로 종료시켜버린다

조건 검증 설계

1. 조건 검증은 먼저 넘어온 문자열의 길이의 절반 크기를 구해 변수로 보관한다
2. 절반만 보면 되는 이유는, 인접한 수열에서 같은 수열이 될 수 있는 최대 길이이기 때문이다
3. 따라서 1부터 len까지 탐색하면서 검증을 진행한다.
4. 현재 문자열 길이 - i랑, 현재 문자열 길이 - 2 * i부터 현재 문자열 길이 - i까지의 문자열이 같은지 확인하고 같다면 좋은 수열이 아니므로 false를 리턴한다
5. 모든 경우를 다 통과하면 true를 리턴한다

정답 코드

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


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        backtracking(n, "");

        br.close();
        bw.close();
    }

    private static void backtracking(int n, String s) {
        if(s.length() == n) {
            System.out.println(s);
            System.exit(0);
        }


        for (int i = 1; i < 4; i++) {
            if(chk(s + i)){
                backtracking(n, s+i);
            }
        }

    }

    private static boolean chk(String s) {
        int len = s.length()/2;

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


        return true;
    }
}

문제 링크

2661번 - 좋은수열