[백준/BOJ] 2661번 좋은수열 자바 풀이

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

2661번: 좋은수열

 

문제

숫자 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들 사이에는 빈칸을 두지 않는다.

 

 

 

DFS의 depth가 깊어질 때마다 1, 2, 3중 하나의 숫자를 append 해준다.

가장 작은 수를 구하는 것이므로 무조건 1로 시작하기 때문에 처음부터 depth을 1, StringBuilder("1")로 전달해주었다.

또한 가장 최근에 append한 문자열을 매개변수(pre)로 전달해줌으로써

동일한 값을 연속적으로 이어붙이지 않도록 해준다. (pre와 동일한 문자열이라면 append하지 않고 continue)

 

처음에는 DFS로 구한 길이 N의 좋은 수열들 모두를 list에 저장하고

DFS가 끝난 후 list를 sort하여 가장 앞의 값을 출력하는 식으로 코드를 작성했는데, 메모리 초과가 떴었다.

아마 재귀적으로 너무 많은 함수가 호출되어서 그런 것 같다. (N이 80이다보니 ...)

 

 

append할 문자열 배열이 "1", "2", "3" 순서로 되어있기 때문에

가장 작은 순서대로 StringBuilder에 append 될 것이다.

즉, 가장 처음으로 발견한 좋은 수열이 가장 작은 값(answer)가 된다.

가장 작은 값을 발견했다면 DFS도 더이상 진행하지 않도록 코드를 작성했다.

 

 

그리고 "1", "2", "3" 완탐이 되지 않도록 

문자를 append 할 때마다 좋은 수열인지 아닌지 확인한다.

check함수를 통해 가장 뒤에서부터 확인한다.

(매개변수 pre를 통해 연속적인 두 문자가 존재하지 않도록 코드를 작성했기 때문에 비교할 문자열 길이가 2 이상인 경우만 비교한다.)

 

 

 

길이가 1~3인 경우는 비교할 문자열이 없다.

길이가 4인 경우 (0~1), (2~3)을 비교한다.

5인 경우 (1~2), (3~4)를 비교한다.

6인 경우 (0~2), (3~5) / (2~3), (4~5)를 비교한다.

7인 경우 (1~3), (4~6) / (3~4), (5~6)을 비교한다.

 

만약 길이가 7일 때 (0~1), (2~3) / (1~2), (3~4) / (2~3), (4~5) 등을 모두 비교하면 

이전에 이미 비교한 것이 중복되어 비효율적이다.

즉, 위와 같이 방금 append한 가장 끝 문자가 포함되는 경우만 비교해주면 된다.

문자열을 반씩 나눠 비교하는 것이므로 

길이가 7인 경우 (7/2 = 3) 비교할 문자열의 길이가 3인 경우부터 2인 경우까지 비교해준다.

만약 길이가 19인 경우 비교할 문자열의 길이가 9인 경우부터 2인 경우까지 끝 문자가 포함되도록 비교해준다.

 

위 설명을 코드로 나타내면 다음과 같다.

 

 

import java.io.*;

public class Main {
	static int N;
	static String[] arr = {"1", "2", "3"};
	static boolean find = false;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		DFS(1, new StringBuilder("1"), "1");
	}
	
	static void DFS(int depth, StringBuilder sb, String pre) {
		if(depth == N) {
			find = true;
			System.out.println(sb);
			return;
		}
		
		for(int i=0;i<3;i++) {
			if(find)
				return;
			
			if(pre.equals(arr[i]))
				continue;
			sb.append(arr[i]);
			int len = sb.length();
			
			if(check(sb.toString(), len)) {
				DFS(depth + 1, sb, arr[i]);
				sb.setLength(len - 1);
			}
			else
				sb.setLength(len - 1);
		}
	}
	
	static boolean check(String str, int len) {
		for(int i=len/2;i>=2;i--) {
			if(str.substring(len - i - i, len - i).equals(str.substring(len - i, len)))
					return false;
		}
		return true;
	}

}