[백준 2661번/JAVA] 좋은 수열 (문제 풀이, 코드)

좋은 수열

좋은수열은 정답 비율이 상당히 높은 문제. 메모리 제한 128MB, 시간 제한 1초이다.나는 부분수열을 비교할때 계속 반복해서 비교해줘서 시간 초과가 날 줄 알았는데 다행히 safe.Java는 최대 384ms 정도 주는 듯 하다. 내 코드는 152ms.

[문제 해석]

인접한 두 개의 부분수열이 같으면 나쁜 수열이다.

수열은 1,2,3 으로만 이루어져있다.

1<=N<=80 길이의 수열 중, 가장 작은 수를 나타내는 수열 출력하기.

 

[풀이]

해당 문제는 백트래킹 알고리즘을 사용한다. 백트래킹이란 간단히 요약해서 어떤 노드를 사용할 수 없게 되면, 더 탐색하지 않고 그 노드의 부모 노드로 돌아가서 다른 노드를 탐색한다.

부모노드 1과 자식노드 1을 붙이면 11이 된다.

11은 1 , 1 이 중복되기 때문에 가능하지 않다.

그러므로 자식노드 1의 자식들을 더 탐색하지 않고 부모노드 1로 돌아가서 다른 자식을 탐색한다.

부모노드 1과 자식노드 2를 붙이면 12가 된다.

자식 노드 2는 가능한 것을 알아냈다. 그럼 자식노드 2의 자식들을 탐색한다.

이런식의 알고리즘을 이용하면 좋은수열 문제를 풀 수 있다.

 

[내 코드 알고리즘]

초기 설정)

제일 먼저 stack 에 순서대로 담을 배열 seq={3,2,1}을 선언해줬다.

그리고 Stringpos 자료형의 Stack을 만들었다. -  문자열의 몇번째 자리인지 나타내는 pos와 해당 문자(3,2,1)을 나타내는 str

 

동작 과정)

1. 스택에 3,2,1을 순서대로 push().
2. pop()한 수를 ans에 append 해준다.
   • ans의 길이==N이면 종료한다.
   • 만약 pop한 Stringpos의 pos값과 ans의 길이가 다르다면, pos값에 도달할 때 까지 ans의 마지막문자(자식노드)를 없애준다.
3. ans의 다음 수로 적합한 수를 탐색하여 3,2,1 순으로 push()
4. 2번으로 돌아간다.

ans의 다음 수로 적합한 수를 탐색하는 법

1. 다음 수가 ans의 마지막 문자의 값과 같다면 적합하지 않은 수.
2. 부분수열의 크기 i인 for문을 만든다. i=2부터 시작.
   • 부분수열이 1인 부분은 1번에서 검사해준셈이다.
   • 동일한 부분수열을 구해야하니까 (ans+다음수 의 길이)/2가 i의 최대값이다.
3. 다음 for문에는 비교할 두 수열중 첫 번째 수열의 시작 위치를 j로 해서 j=0부터 시작.
   
   • 비교대상 1 = j~j+i까지의 문자열.
   • 비교대상 2 = j+i~j+i*2까지의 문자열.
   • ans문자열의 끝에 도달하면 2번의 for문으로 돌아간다.
4. 만약 비교대상 1과 2가 같다면 인접한 동일한 부분 수열이 있는 것이므로 적합하지 않은 수.
5. 아니라면 적합하다!

 

[코드]

import java.util.Scanner;
import java.util.Stack;

class Stringpos {
	int pos;
	String str;
	Stringpos(int p, String s){
		this.pos =p; this.str=s;
	}
}
public class goodseq_2661 {
	static int N;
	static String[] seq = {"3","2","1"};
	static Stack<Stringpos> t;
	static String answer;
	static int len;
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt(); answer ="";
		t = new Stack<>();
		len = 0;
		t.push(new Stringpos(0,"3")); t.push(new Stringpos(0,"2")); t.push(new Stringpos(0,"1"));
		while(true) {
			while(t.peek().pos!=len) {
				answer = answer.substring(0,len-1);
				len--;
			}
			answer += t.pop().str;
			len++;
			if(len==N) break;
			track();
		}
		System.out.println(answer);
	}
	public static void track() {
		for(int i=0; i<3; i++) 
			if(isPossible(seq[i])) t.push(new Stringpos(len,seq[i]));
	}
	public static boolean isPossible(String s) {
		String last = answer.substring(len-1);
		if(last.equals(s)) return false;
		String add = answer + s;
		int size = add.length();
		for(int i=2; i<=size/2; i++) { // 부분 수열의 크기
			for(int j=0; j<size; j++) { // 비교 시작 위치?
				if(j+i>size || j+2*i>size) break;
				String cp1 = add.substring(j,j+i);
				String cp2 = add.substring(j+i,j+2*i);
				if(cp1.equals(cp2)) return false;
			}
		}
		return true;
	}
}

 

[헷갈렸던 점]

처음 짰던 코드에는 Stringpos라는 자료형이 없었다. Stringpos 대신 다음 수로 3,2,1을 다 넣을 수 없다면 ans를 하나 줄이는 방식을 채택했었는데, 이 때문에 N이 일정 값을 넘어가면 정답을 출력할 수 없었다.

Stack의 값을 다 pop할때까지 계속 같은 자리만 맴돌았기 때문이다.고민을 하다가, stack에 push할 때 해당 값이 어느 위치에 들어가야하는 값인지 정보를 주자! 라고 생각했고,이를 구현하니 정답입니다가 나왔다.간단한 실수였는데, 이를 발견하지 못해서 이틀이나 소비했다(...)

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

github.com/MOBUMIN/BJalgorithm/blob/master/goodseq_2661.java

MOBUMIN/BJalgorithm