[백준/JAVA] 2529번 : 부등호(백트래킹, backtracking)

 

 

 

문제

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

2529번: 부등호

 

 

 

풀이

백트래킹 방법으로 문제를 해결할 것이다.

백트래킹 방법은 가지를 탐색하다가 옳지 않으면 바로 다른 가지로 넘어간다.

이 문제에서는 첫번째 자리의 수부터 k+1번째 자리의 수까지 추가해나가며 탐색한다.

탐색 중에 j번째 자리에 넣을 수가 이전 수와의 부등호 조건에 맞지 않으면(ex- 부등호가 <인데 이전 수보다 작은 경우), 바로 다음 경우로 넘어간다.

만약, j번째 자리에 어떤 수를 넣더라도 부등호 조건에 맞지 않으면, j-1번째 자리의 수를 바꾸게 된다.

 

백트래킹으로 탐색하는 과정을 코드로 구현해보면 다음과 같다.

public static void findResult(int idx){
		//모든 자리의 수가 조건을 만족하는 정수를 찾으면 그 정수를 result에 저장한다.
        if(idx == n+1){
            StringBuilder sb = new StringBuilder();
            for(int i : temp)
                sb.append(i);
            result.add(sb.toString());
            return;
        }

        for(int i = 0; i<=9; i++){
        	//이전 자리의 수에서 i가 없어야 하며, 부등호 조건에 만족해야만 한다
            if(!temp.contains(i) && check(i)){
                temp.add(i);
                findResult(idx+1);
                temp.remove(temp.size()-1);
            }
        }
}

 

 

부등호 조건에 만족하는지 확인하는 메서드는 다음과 같이 구현한다.

private static boolean check(int k){
		//0번째 자리의 수를 찾는다면, 부등호가 없으므로 모두 가능하다
        if(temp.isEmpty()) return true;

        int last = temp.get(temp.size()-1);
        String checkSign = sign[temp.size()-1];

		//부등호를 확인하고, 이전 수와 넣으려는 수 k가 부등호 조건을 만족하는지 확인한다
        if(checkSign.equals("<")){
            if(last>k) return false;
        }else if(checkSign.equals(">")){
            if(last<k) return false;
        }
        return true;
}

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static String[] sign;
    static List<Integer> temp = new ArrayList<>();
    static List<String> result = new ArrayList<>();

    public static void findResult(int idx){
        if(idx == n+1){
            StringBuilder sb = new StringBuilder();
            for(int i : temp)
                sb.append(i);
            result.add(sb.toString());
            return;
        }

        for(int i = 0; i<=9; i++){
            if(!temp.contains(i) && check(i)){
                temp.add(i);
                findResult(idx+1);
                temp.remove(temp.size()-1);
            }
        }
    }


    private static boolean check(int k){
        if(temp.isEmpty()) return true;

        int last = temp.get(temp.size()-1);
        String checkSign = sign[temp.size()-1];

        if(checkSign.equals("<")){
            if(last>k) return false;
        }else if(checkSign.equals(">")){
            if(last<k) return false;
        }
        return true;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<n; i++){
            sign[i] = st.nextToken();
        }

        findResult(0);
        System.out.println(result.get(result.size()-1));
        System.out.println(result.get(0));
    }
}

 

 

 

다른 방법

이 문제는 순차탐색의 브루트포스 방법으로도 해결할 수 있다. 이전, 다음 순열을 구해 순차 탐색하는 풀이는 아래에서 확인할 수 있다.

https://sy-zoze.tistory.com/17

[백준/JAVA] 2529번 : 부등호(BruteFroce, 순열)