2529번: 부등호

문제

두 종류의 부등호 기호 < 와 > 가 k개 나열된 순서열 A가 있습니다. 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자(0 ~ 9)를 넣어서 모든 부등호 관계를 만족시키는 k+1 자리의 정수를 만들고자 합니다. 주어진 부등호 관계를 만족하는 정수들 중에서 최댓값과 최솟값을 찾아 출력하는 문제입니다. (단, 첫 자리가 0인 경우에도 0을 생략하지 않고 모두 출력해야 합니다.)

• 입력: 첫 줄에 부등호 문자의 개수 k, 둘째 줄에 k개의 부등호 기호
• 출력: 첫 줄에 최댓값, 둘째 줄에 최솟값 (반드시 k+1 자리의 문자열 형태 유지)

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

풀이: 백트래킹을 이용한 가지치기와 문자열 탐색

이 문제는 0부터 9까지의 숫자 중 중복 없이 k+1개를 고르는 순열 탐색 문제입니다. 앞자리가 0일 수 있으므로 정수형 변수가 아닌 문자열(String)로 상태를 관리하는 것이 중요합니다.

1. 사전순 탐색의 성질 활용: 백트래킹을 0부터 9까지 오름차순으로 진행하므로, 조건을 만족하여 완성된 숫자 문자열들은 자연스럽게 오름차순(사전순)으로 정렬되어 발견됩니다. 따라서 발견되는 문자열들을 리스트에 모두 담은 뒤, 가장 처음에 담긴 것이 최솟값, 가장 마지막에 담긴 것이 최댓값이 됩니다. 복잡한 대소 비교 로직을 없앨 수 있습니다.
2. 가지치기 (Pruning) 적용: k+1개의 숫자를 다 고른 뒤에 부등호를 검사하면 불필요한 경우의 수까지 모두 탐색하게 되어 느려집니다. 숫자를 하나 이어 붙일 때마다, 직전에 붙인 숫자와 지금 붙일 숫자가 해당 자리의 부등호 조건을 만족하는지 즉시 검사합니다. 만족하지 않으면 그 뒤의 탐색은 무의미하므로 바로 건너뜁니다(continue).

코드

import java.io.*;
import java.util.*;

public class Main {
    static int k;
    static String[] a;
    static boolean[] visited = new boolean[10];
    
    // 조건을 만족하는 모든 숫자 문자열을 담을 리스트
    static List<String> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       k = Integer.parseInt(br.readLine());
       a = br.readLine().split(" ");

       // 깊이 0, 빈 문자열로 백트래킹 시작
       go(0, "");

       // 0부터 9까지 오름차순 탐색했으므로
       // 리스트의 마지막 요소가 최댓값, 첫 번째 요소가 최솟값
       bw.write(ans.get(ans.size() - 1) + "\n");
       bw.write(ans.get(0) + "\n");

       bw.flush();
       bw.close();
       br.close();
    }

    static void go(int depth, String s) {
       // k+1개의 숫자를 모두 골랐다면 정답 리스트에 추가
       if (depth == k + 1) {
          ans.add(s);
          return;
       }

       for (int i = 0; i <= 9; i++) {
          if (visited[i])
             continue;
             
          // 가지치기: 첫 번째 숫자가 아닐 경우, 직전 숫자와 현재 숫자 i의 부등호 관계 확인
          if (depth > 0) {
              int prev = s.charAt(depth - 1) - '0';
              if (!check(prev, i, a[depth - 1])) {
                  continue; // 조건을 만족하지 않으면 더 이상 깊이 탐색하지 않음
              }
          }
          
          visited[i] = true;
          // 문자열 연산을 통해 현재 숫자를 이어 붙이고 다음 깊이로 이동
          go(depth + 1, s + i);
          visited[i] = false; // 백트래킹 (원상 복구)
       }
    }

    // 부등호 방향에 따라 두 숫자의 대소 관계가 올바른지 판단
    static boolean check(int prev, int curr, String op) {
       if (op.equals("<")) return prev < curr;
       return prev > curr;
    }
}

알고리즘 분류

브루트포스 알고리즘 (완전탐색), 백트래킹 (Backtracking)