[BOJ] 백준 2661. 좋은 수열

문제

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

 

---

풀이

백트래킹을 활용한 문제입니다. 

 

 처음에 문제를 보고 정말 많이 헤맸는데, 숫자형으로 표현해야한다는 무의식적인? 고집이 있었습니다. 수열이다보니 숫자로 어떻게 조합을 잘 해야겠다라고 생각한 것이 시간을 많이 잡아먹었습니다.

 

 

  이 문제에서 포인트가 두 가지가 있다고 생각합니다.  첫 번째는 나타낼 수열을 String으로 받는 것, 그리고 좋은 수열인지 아닌지를 어떻게 판단할지입니다.

 

 전체적인 구조는 백트래킹 메서드의 매개변수를 String 형의 수열로 받아, 좋은 수열이 맞다면 다시 재귀를 돌려주는 방식입니다.

 

 좋은 수열인지를 판단하는 메서드는 String을 subString으로 나누어 반복문을 돌며 구간 검사를 진행하면 됩니다. 만약 반복되는 순열 부분이 있다면 false를 리턴해줍니다.

 

 

 아래는 소스 코드입니다.

---

소스 코드

import java.util.Scanner;

public class B2661_좋은수열 {
    static int N;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        backTracking("");
    }
    
    static void backTracking(String str){
        if(str.length() == N){
            System.out.println(str);
            System.exit(0);
        }
        else{
            for(int i = 1; i<=3;i++){
                if(isNice(str+i)) backTracking(str+i);
            }
        }
    }

    static boolean isNice(String str){
        for(int i = 1; i<=str.length()/2;i++) {
            String front = str.substring(str.length()-2*i,str.length()-i);
            String back = str.substring(str.length()-i, str.length());
            if(front.equals(back)) return false;
        }
        return true;
    }
}