[백준] 2529. 부등호

문제 링크

[백준] 2529. 부등호

풀이 과정

완전 탐색 문제로, 재귀 함수를 사용해 문제를 해결했습니다.

static int K;
static String[] oper;
static boolean[] used;
static String max = "0", min = "9876543210";

사용한 전역 변수들입니다.

• 배열 oper 에는 입력받는 K개의 부등호를 순서대로 저장합니다.
• 배열 used 는 재귀 호출 동안 0부터 9까지의 숫자의 사용 유무를 저장합니다.
• max 는 재귀 호출이 끝난 시점에 완성된 숫자 중 가장 큰 수를, min 은 가장 작은 수를 담습니다. 첫자리가 0인 경우를 위해 문자열로 선언해 주었습니다.

for (int i = 0; i <= 9; i++) {
    used[i] = true;
    dfs(0, String.valueOf(i), i);
    used[i] = false;
}

이어 붙일 숫자의 맨 처음 숫자를 미리 정해두고 dfs() 를 호출합니다.

static void dfs(int idx, String s, int prev) {
    if (idx == K) {
        max = Long.parseLong(s) > Long.parseLong(max) ? s : max;
        min = Long.parseLong(s) < Long.parseLong(min) ? s : min;

        return;
    }

    for (int i = 0; i <= 9; i++) {
        if (used[i]) continue;

        if ((oper[idx].equals("<") && prev < i) || (oper[idx].equals(">") && prev > i)) {
            used[i] = true;
            dfs(idx + 1, s + i, i);
            used[i] = false;
        }
    }
}

dfs() 는 다음 세 개의 인자를 받습니다.

• idx 는 이번 함수 호출에서 사용할 부등호를 가리키는 인덱스입니다.
• s 는 이전까지 이어 붙인 숫자를 의미합니다.
• prev 는 바로 전 단계에서 부등호 비교를 위해 사용된 피연산자를 의미합니다.

dfs()는 다음과 같이 동작합니다.

1. for문을 통해 0부터 9까지의 숫자를 돌며 아래와 같은 과정을 거칩니다.
   • 해당 숫자 i 가 사용되었다면, 사용 가능한 다음 숫자를 찾기 위해 continue 합니다.
   • 현재 재귀 스택까지 사용되지 않았다면, 먼저 i 로 올바른 부등호 비교가 가능한 지 확인합니다. 해당 숫자를 채택할 수 있다면, 사용 처리를 한 뒤 재귀 함수를 호출합니다. 이 때, 다음 부등호를 가리키는 인덱스, 현재 채택한 숫자를 이어붙인 새로운 숫자를 의미하는 문자열 및 현재 숫자를 전달합니다.
2. idx 가 배열 oper 의 범위를 벗어나는 순간, 즉 idx == K 이면, 최대값과 최소값을 갱신해줍니다. 만들어질 수 있는 가장 큰 수 s 는 9876543210로 int 범위를 넘어가므로, parseLong() 을 통해 비교해줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int K;
    static String[] oper;
    static boolean[] used;
    static String max = "0", min = "9876543210";

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

        for (int i = 0; i <= 9; i++) {
            used[i] = true;
            dfs(0, String.valueOf(i), i);
            used[i] = false;
        }

        System.out.println(max + "\n" + min);
    }

    static void dfs(int idx, String s, int prev) {
        if (idx == K) {
            max = Long.parseLong(s) > Long.parseLong(max) ? s : max;
            min = Long.parseLong(s) < Long.parseLong(min) ? s : min;

            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (used[i]) continue;

            if ((oper[idx].equals("<") && prev < i) || (oper[idx].equals(">") && prev > i)) {
                used[i] = true;
                dfs(idx + 1, s + i, i);
                used[i] = false;
            }
        }
    }
}