백준 2529 부등호 Java

그리디에서 발견한 문제이지만 그리디로 해법을 찾지 못하고

검색을 해보니 많은 분들이 백트래킹을 통해 풀었길래 백트래킹으로 풀어본 문제이다.

 

문제는

부등호의 길이 n과 n개의 부등호가 주어지면

그 부등호를 만족하는 정수 n+1개 중에 최솟값과 최댓값을 출력하면 되는 문제이다.

 

아직 백트래킹이 어렵게 느껴진다.

되돌려서 되추적 하는 것이 핵심이라는 것만 알고 있다.

이 문제에서도 똑같이 적용했다.

 

백트래킹을 통해 길이가 n+1인 가능한 경우를 모두 재귀 호출로 만들어보고

그 문자열이 부등호를 만족하는지 체크해서 ArrayList에 넣었다.

그 후 첫 번째 값과 마지막 값을 출력하는 방식으로 풀었다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q2529 {
    static List<String> list = new ArrayList<>();
    public static boolean check(String key, String [] s) { //부등호를 만족하는 지 체크하는 메소드
        for(int i=1; i<key.length(); i++) {
            if(s[i-1].equals("<")) {
                if(!(key.charAt(i-1)-'0' < key.charAt(i)-'0')) {
                    return false;
                }
            }
            else {
                if(!(key.charAt(i-1)-'0' > key.charAt(i)-'0')) {
                    return false;
                }
            }
        }
        return true;
    }
    
    public static void go(String[] s, boolean [] visited, String key, int size){
        if(key.length() == size) {
            if(check(key, s)) {
                list.add(key);
            }
            return;
        }
        if(key.length() > size )
            return;
        for(int i=0; i<=9; i++) {
            if(!visited[i]) {
                visited[i] = true;
                go(s, visited, key+i, size);
                visited[i] = false; //백트래킹을 위한..
            }
        }
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        String [] s = scan.nextLine().split(" ");
        boolean [] visited = new boolean[10];
        
        go(s,visited, "", n+1);
        
        System.out.println(list.get(list.size()-1));
        System.out.println(list.get(0));
    }
 
}

 

통과는 했지만 다른 분들의 코드와 비교해보니 현저히 느린 코드였다.

그래서 검색을 통해 어떻게 하면 더 빠르게 해결할 수 있을지 찾아보았다.

마이구미님의 블로그에서 더 빠른 코드를 찾을 수 있었다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q2529_ver2 {
    static List<String> list = new ArrayList<>();
    static boolean [] visited = new boolean[10];
    static String [] s;
 
    public static void go(int num, int cnt, String key, int n) {
        if(cnt == n) {
            list.add(key);
        }
        else {
            for(int i=0; i<=9; i++) {
                if(!visited[i]) {
                    if(s[cnt].equals("<")) {
                        if(num>=i) {
                            continue;
                        }
                    }
                    else {
                        if(num<=i) {
                            continue;
                        }
                    }
                    visited[i]= true;
                    go(i, cnt+1, key+i, n);
                }
            }
        }
        visited[num] = false;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        s = scan.nextLine().split(" ");
 
        for(int i=0; i<=9; i++) {
            visited[i] = true;
            go(i, 0, i+"", n);
        }
        
        System.out.println(list.get(list.size()-1));
        System.out.println(list.get(0));
    }
}

 

내가 짠 코드와 시간이 왜 이렇게 차이가 날까 생각해봤다.

우선 나는 O(n)인 check 메소드를 통해 부등호를 만족하는지 검사했는데

여기서는 부등호를 검사하면서 백트래킹을 진행한다. O(n)만큼의 시간이 빨라지는 것이다.

또한 0부터 9까지 앞자리를 바꿔가면서 백트래킹을 진행하는 대신에

재귀 호출의 깊이? 가 n을 넘어가지 않는다. 그리고

메소드의 마지막에만 백트래킹을 위한 코드를 넣어서 문자열에 중복되는 수도 없게 했다.

 

많이 배웠다. 연습을 더 많이 해야겠다..