문제
숫자 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들 사이에는 빈칸을 두지 않는다.
풀이
조건을 만족하는 수열을 사전순으로 가장 작게 만들어야 하므로, 앞에서부터 1, 2, 3 순서로 붙여 보며 백트래킹하면 된다.
중요한 점은 끝까지 다 만든 뒤 검사하면 너무 느리다는 것이다. 그래서 숫자를 하나 붙일 때마다 현재 접미사에서 같은 길이의 인접 부분 수열이 생겼는지 바로 확인해야 한다.
코드의 check()는 문자열 끝부분만 검사한다. 길이 i인 부분 수열이 두 번 연속 등장하는지만 보면 되므로, 마지막 i개와 그 앞의 i개를 비교하면 충분하다. 하나라도 같으면 그 분기는 즉시 버린다.
그리고 1 -> 2 -> 3 순서로 DFS를 돌리다가 처음 완성되는 수열이 곧 정답이다. 사전순으로 가장 작은 수열을 따로 비교할 필요가 없는 이유다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
solve(0, "");
System.out.println(sb);
}
static boolean solve(int idx, String str) {
if (idx == N) {
sb.append(str);
return true;
}
for (int i = 1; i <= 3; i++) {
if (check(str + i)) {
if (solve(idx + 1, str + i)) {
return true;
}
}
}
return false;
}
static boolean check(String str) {
int len = str.length() / 2;
for (int i = 1; i <= len; i++) {
if (str.substring(str.length() - i)
.equals(str.substring(str.length() - i * 2, str.length() - i)))
return false;
}
return true;
}
}복잡도
- 시간 복잡도: 좋은 수열 후보를 백트래킹하므로 최악의 경우 이다.
- 공간 복잡도: 현재 수열과 재귀 스택을 저장하므로 이다.
마무리
좋은 수열 문제는 결국 "나쁜 패턴이 보이면 바로 자르기"가 핵심이다. 끝부분만 빠르게 검사하는 가지치기 덕분에 사전순 DFS로도 충분히 해결된다.
