[백준]2661: 좋은 수열 - JAVA

[백준]2661: 좋은 수열 

2661번: 좋은수열

풀이

문제의 조건에 제시된 좋은 수열의 조건을 만족하면서 가장 작은 N자릿수 를 반환하는 문제이다.

 

뽑을 수 있는 범위의 숫자는 1~3 밖에 없으므로 start 값을 1, end 값을 3으로 지정하였다. 

 

숫자를 하나씩 뽑는 과정을 backtracking 함수라고 이름 붙였지만, 조건에 맞는 수를 확인하며 하나씩 뽑아주기 때문에 백트랙킹 보다는 순차적으로 순열 방법으로 수를 뽑아준 풀이라고 봐야 할 것 같다. (이럴거면 이름을 permutation으로 바꿔버릴걸 그랬당)

 

1 ~ 3 중에 하나의 수를 뽑아 나간다고 할 때 가장 작은수부터 뽑고 (문제의 조건), 뽑고 난 후의 수열이 좋은 수열일 때에만 탐색을 계속 진행하였다.

 

뽑고 난 후의 수열이 좋은 수열인지 판별하는 함수는 can_make_str이라고 이름 붙였다. 좋은 수열인지 판별하는 방법을 알아보자.

현재 str을 기준으로 새로 뽑은 마지막 문자를 제외하곤 좋은 수열인 상태이다. 그러므로 마지막 문자와 연관된 부분만 좋은 수열이 되는지 확인하면 된다.

 

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

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

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

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

 

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

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

 

이때 '맨 마지막 문자를 포함한 i길이의 문자열' 을 back이라고 부르고, '그 크기 만큼의 바로 앞 문자열' 을 front라고 해보자. 

🔹 back을 구하기 위해선 전체 문자열에서 마지막 i 길이 만큼 잘라주면 된다. 아래와 같은 식을 도출할 수 있다.

back = str.substring(str.length() - i, str.length());

🔹 front를 구히가 위해선 back의 앞 부분에서 i 길이 만큼 잘라주면 된다. 아래돠 같은 식을 도출할 수 있다. 

front = str.substring(str.length() - i * 2, str.length() - i);

 

코드

import java.util.*;
 
public class Main {
    
    static int start = 1;
    static int end = 3;
    static int n;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        backtracking("");
    }
 
    public static void backtracking(String str) {
        if(str.length() == n) {
            System.out.println(str);
            System.exit(0);
        }
 
        for(int i = start; i <= end; i++) {
            if(can_make_str(str + i)) backtracking(str + i);
        }
    }
 
    public static boolean can_make_str(String str) {
        for(int i = 1; i <= str.length() / 2; i++) {
            String front = str.substring(str.length() -i * 2, str.length() - i);
            String back = str.substring(str.length() - i, str.length());
            if(front.equals(back)) return false;
        }
        return true;
    }
}