링크

2661 좋은 수열

문제

설명

이 문제는 백트래킹을 통해 문제를 풀 생각은 했다.
나쁜 수열을 체크하는 방법에서 막혔다. 왜냐하면 처음부터 체크하는 방법을 생각했었는데 이 방법은 시간복잡도가 O(n2)이였기 때문이다.

그래서 다른분들의 블로그를 찾아보니 뒤에서 부터 수행하면 O(n)으로 찾을 수 있었다.
예를 들어 1212가 있으면 인덱스가 3인 2부터 하나씩 길이를 늘려가면서 비교하는 방법이다.

코드

핵심 코드

DFS

    public static void dfs(int n, String str){
        if(str.length() == n){
            //System.out.println(list);
            System.out.println(str);
            System.exit(0);
        }

        for(int i=1;i<=3;i++){
            if(check(str+i)){
                dfs(n, str + i);
            }
        }
    }

재귀를 통해 문자열을 만들어준다.
중간에 check함수를 통해 만족하면 재귀를 실행한다.

좋은 수열인지 체크

public static boolean check(String str){

        //뒤에서 부터 체크
        for(int i=1;i<=str.length()/2; i++){
            String back = str.substring(str.length() - i, str.length());
            String front = str.substring(str.length() - (2*i), str.length() - back.length());

            if(front.equals(back)) return false;
        }

        return true;

    }

기존 문자열에서 1, 2, 3중 하나를 붙였을 때 나쁜수열인지 좋은 수열인지 체크하는 메소드이다.
121321이 있으면
맨 처음 i가 1일때 맨 뒤에 하나 1을 잘라 back에 넣고
맨 뒤에서 바로 앞인 2를 front에 넣어 비교한다.

i가 2면 front는 맨 뒤에서 2개, back도 front를 제외한 맨 뒤에서 2개를 비교하면 된다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Algorithm {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        dfs(n, "");



    }

    public static void dfs(int n, String str){
        if(str.length() == n){
            //System.out.println(list);
            System.out.println(str);
            System.exit(0);
        }

        for(int i=1;i<=3;i++){
            if(check(str+i)){
                dfs(n, str + i);
            }
        }
    }

    public static boolean check(String str){

        //뒤에서 부터 체크
        for(int i=1;i<=str.length()/2; i++){
            String back = str.substring(str.length() - i, str.length());
            String front = str.substring(str.length() - (2*i), str.length() - back.length());

            if(front.equals(back)) return false;
        }

        return true;

    }

}