[백준 2661] - [백트래킹] - 좋은 수열 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2661

---

이 문제는 아주 쉽게 백트래킹으로 접근 할 수 있다. 

모든 경우의 수를 탐색하면서 조건에 성립되면 결과를 출력하면 된다.

이 문제에서 제시하는 조건은 다음과 같다.

• 임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않아야 한다. (나쁜 수열이면 안된다.)
• 나올 수 있는 좋은 수열 중에서 가장 작은 수를 출력해야 한다.

첫번째 조건을 확인하는 함수 하나를 만들고 두번째 조건은 첫번째로 좋은 수열이 나온 좋은 수열이 제일 작은 수열이기 때문에  좋은 수열이 나오면 모든 탐색을 종료 시키면 되기 때문에 따로 조건을 확인하는 함수를 만들 필요는 없다. 

좋은 수열인지 확인하는 함수는 아래와 같이 만들었다.

public static boolean isAble(String str) {

int len = str.length();

// 1212 가 들어올 경우

// 한글자씩 비교 했을 경우에는 유효하지만

// 두글자씩 비교 했을 경우에는 12 12 가 같으므로 유효하지 않다. 

for(int i = 1; i <= len/2; i++) {

String front_str = str.substring(str.length()-i-i, str.length()-i);

String behind_str = str.substring(str.length()-i, str.length());

if(front_str.equals(behind_str)) return false;

}

return true;

}

수열이 작성된 String 문자열을 맨 위에서 부터 문자열 길이의 절반까지  반복하면서 비교하려는 두개의 문자열을 추출한 뒤 그 두 문자열이 같으면 나쁜 수열로 인지하고 false를 반환하는 함수이다.

이 문제에서 제일 중요한 부분이 이 함수이다. 

나머지는 기본 백트래킹대로 소스를 작성하면 된다.

소스

import java.util.Scanner;
 
public class Main {
    
    public static final int START = 1;
    public static final int END = 3;
    
    public static int len;
    public static int[] arr;
    public static boolean is_end = false;
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        len = sc.nextInt();
        
        arr = new int[len];
        
        backtracking("");
    }
    
    public static void backtracking(String str) {
        if(is_end) return;
        
        if(str.length() == len) {
            System.out.println(str);
            is_end = true;
            
            return;
        }
        
        for(int i= START; i <= END; i++) {
            if(isAble(str+i)) {
                backtracking(str+i);
            }
        }
    }
    public static boolean isAble(String str) {
        int len = str.length();
        // 1212 가 들어올 경우
        // 한글자씩 비교 했을 경우에는 유효하지만
        // 두글자씩 비교 했을 경우에는 12 12 가 같으므로 유효하지 않다. 
        for(int i = 1; i <= len/2; i++) {
            String front_str = str.substring(str.length()-i-i, str.length()-i);
            String behind_str = str.substring(str.length()-i, str.length());
            
            if(front_str.equals(behind_str)) return false;
        }
        
        return true;
    }
}