[백준] 2661 좋은수열 - 백트래킹(Backtracking) + 문자열(String) + 아이디어(Idea) JAVA

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

2661번: 좋은수열

코드설명

백트래킹, 문자열 아이디어 문제입니다.

 

이 문제같은경우 1 2 3 으로 모든 순열을 구하는 완전탐색을 진행하면서,

시간을 줄이기 위해 옳은 조건일시에만 완전탐색을 진행해야합니다. 

 

이 문제에서 123 으로 N 길이의 수열을 구하는것은 어렵지 않습니다.

이 문제에서 유의해야할점은, 각 수열이 좋은 수열인지 판단하는 로직입니다.

 

아래의 로직은 해당 로직입니다.

for(int length = 1; length <= sb.length() / 2; length ++) {
    String first = sb.substring(sb.length() - length * 2, sb.length() - length);
    String second = sb.substring(sb.length() - length ,sb.length());
    if(first.equals(second)) {
        return ;
    }
}

• 위의 로직은 수열을 구할때마다 실행됨으로써 애초에 잘못된 수열이 완전탐색되지 않도록하여 시간을 줄여줍니다. 
• 모든 로직마다 수열이 실행되기에 새롭게 추가된 마지막 문자의 기준으로만 좋은수열인지 판단하면, 모든 경우를 판단한 것과 같습니다.

위의 예시를 들어보면,

 

4 를 넣었을 경우를 생각해보겠습니다.

1 -> PASS

11 -> FAIL  (first: "1", second:"1") 같으므로 FAIL

12 -> PASS  (first:"1", second:"2")

121 -> PASS (first: "2", second:"1" 다르니 PASS )

      --> 1 2 1 에서 뒤의 2 1 만 비교해도됩니다. 1 2 는 이미 앞의 단계에서 비교

1212 -> PASS (first: "1", second:"2" 다르니 PASS )

          ->FAIL (first:"12", second:"12" 같으므로 FAIL)  

1213 -> PASS (first: "1", second:"3" 다르니 PASS)

         -> PASS (first:12", second:"13") 다르니 PASS)

 1213 이 정답입니다.

 

위와 같이 1213 을 진행했을때,

두가지경우만 비교해도 됩니다. (1과 3을 비교하고, 12와 13을 비교)

앞에서 이미 다른경우들은 비교하고 왔으므로 이미 좋은 수열입니다.

 

이런식으로 이미 검사했던 경우를 생각할경우 구현도 훨씬 간단해지므로, 위의 로직을 기억해두는게 좋을 것 같습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		simulate(0);
	}
	
	public static void simulate(int level) {
		
		//뒤에서부터 검사한다.
		//현재 길이가 만약 7과 같다면, 1234567 에서 234 567 만 검사하면된다. 굳이 123 456 은 검사할 필요없다. 
		// 이미 그 전 단계에서 해당 길이를 검사하고 왔기 때문이다. 뒤에서부터 각 길이당 한개씩 검사하면 된다.
		for(int length = 1; length <= sb.length() / 2; length ++) {
			String first = sb.substring(sb.length() - length * 2, sb.length() - length);
			String second = sb.substring(sb.length() - length, sb.length());
			
			if(first.equals(second) == true){
				return ;
			}
		}
		
		if(level >= N) {
			System.out.println(sb.toString());
			System.exit(0);
			return ;
		}
		
		for(int i=1; i<=3; i++) {
			sb.append(i);
			simulate(level + 1);
			sb.deleteCharAt(sb.length() - 1);
		}
	}
	
}

 

시간이 오래걸리는 코드. 나쁜 수열을 모든 부분에 대해 적용하기에 시간이 오래걸립니다.

public static boolean checkBadPerm() {
    //각 자리마다 진행할 것 입니다.
    //시작점을 기준으로 가 아닌, distance로 감싸면서 시작해야 더 편리합니다.
    for(int distance=1; distance <= sb.length() / 2; distance++) {
        for(int start = 0; start < sb.length() - distance; start++){
            if(start + distance + distance > sb.length()) continue; //마지막 부분이 초과되는경우 고려
            String str1 = sb.substring(start, start + distance);
            String str2 = sb.substring(start + distance, start + distance + distance);
 
            System.out.println("str1:"+str1);
            System.out.println("str2:"+str2);	
        }
 
    }	
 
    return true;
}

 

틀린 코드

각 문자열을 돌면서 나쁜수열인지 판단하려고 한 코드 ( 나쁜수열판단 코드를 구현중에 복잡한 로직이여서 구현중에 위의 방식으로 순회했습니다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int[] arr;
	public static int answer = 0;
	public static int cnt = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[7]; 
    			
    	simulate(0, 0);
    	
    	System.out.println(answer);
    }
    
    public static void simulate(int idx, int level) {
    	System.out.println("LEVEL:"+level);
    	
    	if(level == N) {
    		for(int i=0;i<N;i++) {
    			System.out.print(arr[i]+" ");
    		}
    		System.out.println();
    		return ;
    	}
    	
    	
    	for(int length = 1; length < level/2 + 1; length++) {
    		for(int i=0; i < level - length; i++) {
    			int sameCnt = 0;
    			for(int j=0; j < length; j++) {
    				if(arr[i+j] == arr[i+j+length]) {
    					sameCnt += 1;
    				}
    			}
    			if(sameCnt == length) return;
    		}
    	}
    
    	
    	
    	for(int i=1;i<=3;i++) {
    		//1, 2, 3을 넣는경우 (이전에 넣었던 값을 기억해서 불필요 연산제거)
    		if(arr[level] == 0) {
        		arr[level] = i; 
        		simulate(i + 1 , level + 1);
        		arr[level] = 0;    			
    		}
    	}
    	
    	
    }
    
   
}