[백준] 좋은수열 2661 - JAVA

문제

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

2661번: 좋은수열

 

풀이

백트레킹 문제이다.

숫자를 하나씩 뽑으면서 인접한 두 개의 부분 수열이 동일한 것이 있는지 확인하면 된다.

 

좋은 수열인지 판별하는 방법은 다음과 같다. 

현재 str은 새로 뽑은 마지막 문자를 제외하면 좋은 수열인 상태이다.

따라서 마지막 문자만 연관된 부분이 좋은 수열인지 판별하면 된다.

 

이를 반복문과 sustring을 활용하여 구현하였다. 

예를들어 1212라는 수열이 전달되었을때를 확인해보자. 마지막 문자인 '2'와 연관된 부분만 확인하면 된다.

1. 1212중에서 '2'와 그 바로 앞 '1'이 같은지 확인한다.
2. 1212중에서 '12'와 그 바로 앞 '12'이 같은지 확인한다.

해당 두 부분만 확인하면 된다. 

 

확인할 문자열의 길이는 1부터 시작하여 전체 문자열의 길이의 절반 까지만 확인하면 된다. 

substring으로 나눠 비교해줄 두 부분의 문자열은 맨 마지막 문자를 포함한 i길이의 문자열과, 그 크기 만큼의 바로 앞 문자열을 비교하면 된다. 

 

코드

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

public class Main {
		
	static int n;
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		n = Integer.parseInt(br.readLine());
		
		back("");
		
	}
   
	static void back(String str) {
		if(str.length() == n) {
			System.out.print(str);
			System.exit(0);
		}
		for(int i=1;i<=3;i++) {
			if(checkArr(str + i)) {
				back(str+i);
			}
		}
	}
	
	static boolean checkArr(String s) {
		for(int i = 1; i <= s.length() / 2 ; i++) {
			String front = s.substring(s.length() - i);
			String back = s.substring(s.length() - 2*i, s.length() - i);
			if(front.equals(back)){
				return false;
			}
		}
		return true;
	}
   
}