백준-2529번/부등호 (java)

 

 

문제 이해

 

부등호로 이루어진 문자열이 주어지면 부등호 사이에 올수있는 모든 숫자열 중 최솟값과 최대값을 구해주면 된다.

모든 경우를 구해줘야 하므로 dfs를 이용하면 쉽게 구할 수 있다.

 

문제 풀이

 

<Main 함수>

맨 앞의 숫자가 0~9까지 중 올수있는 모든 경우의 수를 구해줘야 하므로 for문을 이용하여 dfs를 호출해준다.

for (int i = 0; i < 10; i++) {
    visit[i] = true;
    dfs(i, 0, i + "");
    visit[i] = false;
}

 

<dfs 함수>

 

※매개변수

start ==>가장 최근에 삽입된 숫자(dfs에서는 start뒤에 들어올 숫자를 결정)

count ==> 삽입된 숫자의 갯수

num ==> 부등호 사이에 들어가는 숫자들을 표현한 문자열

static void dfs(int start, int count, String num) {
    if (count == N) {
        number.add(num); //숫자가 완성된 경우 ArrayList에 추가
        return;
    }

    for (int i = 0; i < 10; i++) {
        if (!visit[i]) { // 사용되지 않은 숫자만 사용
            if (S[count].equals("<")) {// <뒤에는 start보다 큰 숫자만 올수 있다.
                if (start < i) {
                    visit[i] = true; // 삽입할 숫자를 방문 표시
                    dfs(i, count + 1, num + i);
                    visit[i] = false;
                }
            } else {
                if (start > i) { //>뒤에는 i가 start보다 작을 경우만 삽입할 수 있다.
                    visit[i] = true;
                    dfs(i, count + 1, num + i);
                    visit[i] = false;
                }
            }
        }
    }
}

 

S[count]가 '<'면 다음에 삽입할 숫자는 start보다 큰 수를 삽입해야 한다.

따라서 start보다 큰 i를 삽입하여 dfs를 재귀적으로 호출해준다.

 

S[count]가 '>'면 다음에 삽입할 숫자는 start보다 작은 숫자를 삽입해야 한다.

따라서 start보다 작은 i를 삽입하여 dfs를 재귀적으로 호출해준다.

 

dfs 종료 조건 : count가 N과 같아지면 부등호 사이에 모든 숫자를 넣었다는 뜻이므로 문자열 num을 ArrayList에 넣어준다.

 

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Problem2529 {
    static int N;
    static String[] S; //부등호
    static boolean[] visit; //0부터 9까지의 숫자 사용 여부
    static ArrayList<String> number = new ArrayList<>(); //가능한 모든 경우의 숫자열을 담아두는 ArrayList

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = br.readLine().split(" ");
        visit = new boolean[10];

        for (int i = 0; i < 10; i++) {
            visit[i] = true;
            dfs(i, 0, i + "");
            visit[i] = false;
        }
        Collections.sort(number);
        System.out.println(number.get(number.size() - 1));
        System.out.println(number.get(0));
    }

    static void dfs(int start, int count, String num) {
        if (count == N) {
            number.add(num); //숫자가 완성된 경우 ArrayList에 추가
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (!visit[i]) { // 사용되지 않은 숫자만 사용
                if (S[count].equals("<")) {// <뒤에는 start보다 큰 숫자만 올수 있다.
                    if (start < i) {
                        visit[i] = true; // 삽입할 숫자를 방문 표시
                        dfs(i, count + 1, num + i);
                        visit[i] = false;
                    }
                } else {
                    if (start > i) { //>뒤에는 i가 start보다 작을 경우만 삽입할 수 있다.
                        visit[i] = true;
                        dfs(i, count + 1, num + i);
                        visit[i] = false;
                    }
                }
            }
        }
    }
}