알고리즘 | 백트래킹 | Java 백준[Silver I] 부등호 - 2529

[Silver I] 부등호 - 2529

문제 링크

성능 요약

메모리: 26648 KB, 시간: 132 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 9월 28일 12:51:50

문제 설명

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다.

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

풀이

이 문제는 DFS(깊이 우선 탐색)을 활용하여 주어진 부등호 조건을 만족하는 숫자 조합을 찾는 문제입니다. 문제의 핵심은 부등호 기호 앞뒤에 서로 다른 숫자를 배치하여 가능한 최대값과 최소값을 구하는 것입니다.

DFS 접근법

1. 문제 개요

   • 주어진 부등호 기호가 k개일 때, 우리는 서로 다른 숫자를 부등호 관계에 맞게 배치하여 (k+1) 자리의 숫자를 만들어야 합니다.
   • 가능한 숫자는 0부터 9까지이며, 중복 없이 사용해야 합니다.
   • 조건을 만족하는 수 중에서 최댓값과 최솟값을 구하는 것이 목표입니다.

2. DFS 구현

   • DFS를 통해 숫자를 하나씩 선택하면서, 부등호 조건을 만족하는지 확인합니다.
   • visited 배열을 사용해 이미 선택된 숫자를 다시 선택하지 않도록 합니다.
   • 모든 숫자가 선택되면 해당 조합을 저장합니다.

3. 알고리즘 흐름

   • DFS를 통해 가능한 모든 숫자 조합을 탐색하면서, 주어진 부등호 조건을 만족하는 경우에만 결과 리스트에 저장합니다.
   • 최종적으로 결과 리스트에서 최댓값과 최솟값을 찾아 출력합니다.

DFS 구현 흐름

1. 숫자 선택과 조건 체크

   • DFS는 첫 번째 숫자부터 시작하여 하나씩 숫자를 선택합니다.
   • 선택한 숫자가 부등호 조건을 만족하는지 확인한 후, 조건을 만족하면 다음 숫자를 선택하고, 만족하지 않으면 백트래킹합니다.

2. 모든 숫자를 선택한 경우 결과 저장

   • 모든 숫자를 선택하면 그 숫자를 결과 리스트에 저장합니다.
   • 이 과정을 반복하여 가능한 모든 숫자 조합을 찾습니다.

코드 설명

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

public class Main {
    public static int k;
    public static String[] signs;  // 부등호 기호 배열
    public static boolean[] visited;  // 숫자 사용 여부 확인 배열
    public static List<String> results = new ArrayList<>();  // 가능한 결과 저장 리스트

    // DFS를 이용한 백트래킹 함수
    private static void DFS(int count, String num) {
        if (count == k + 1) {  // k개의 부등호를 만족하는 숫자를 모두 선택했다면
            results.add(num);  // 결과 리스트에 추가
            return;
        }

        for (int i = 0; i <= 9; i++) {  // 0부터 9까지 숫자를 선택
            if (!visited[i]) {  // 아직 사용하지 않은 숫자라면
                if (count == 0 || checkCondition(num.charAt(count - 1) - '0', i, signs[count - 1])) {  // 부등호 조건을 만족한다면
                    visited[i] = true;  // 숫자 사용 체크
                    DFS(count + 1, num + i);  // 다음 숫자를 선택
                    visited[i] = false;  // 백트래킹 (다시 숫자 사용 가능 상태로 변경)
                }
            }
        }
    }

    // 부등호 조건을 체크하는 함수
    private static boolean checkCondition(int a, int b, String sign) {
        if (sign.equals("<")) {
            return a < b;
        } else {
            return a > b;
        }
    }

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

        k = Integer.parseInt(br.readLine());  // 부등호 개수
        signs = br.readLine().split(" ");  // 부등호 배열
        visited = new boolean[10];  // 숫자 0~9의 사용 여부

        DFS(0, "");  // DFS 시작 (0번째 숫자부터 시작)

        // 결과 리스트에서 최댓값과 최솟값 찾기
        Collections.sort(results);  // 결과를 오름차순으로 정렬
        System.out.println(results.get(results.size() - 1));  // 최댓값 출력
        System.out.println(results.get(0));  // 최솟값 출력
    }
}

최종 흐름

1. main 함수에서 입력 처리

   • 부등호 개수 k와 부등호 기호 배열을 입력받아 DFS를 호출합니다.

2. DFS를 통한 숫자 선택

   • DFS를 통해 숫자를 하나씩 선택하며, 조건을 만족하는 경우만 다음 숫자로 넘어갑니다.

3. 결과 처리

   • 모든 가능한 숫자 조합을 구한 후, 이를 정렬하여 최댓값과 최솟값을 출력합니다.

[공부한 내용 중 고민했던 점]

부등호 조건을 만족하는 숫자 조합을 찾기 위해 DFS와 백트래킹을 활용하는 방법이 적합했습니다. 다만, 숫자가 최대 10개이므로 DFS 깊이가 깊어질 때의 성능 문제를 고민했지만, 문제의 제한 범위가 작기 때문에 충분히 처리 가능하다고 판단했습니다.