[백준] 2529 부등호 (JAVA)

문제 링크:

2529번: 부등호

 

 

난이도: 실버 1

 

 

문제:

두 종류의 부등호 기호 ‘<’와 ‘>’가 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

 

 

문제 이해:

처음 문제를 읽었을 때, 이해 자체는 어렵지 않다.

주어지는 것은 부등호의 개수와 부등호들의 나열이다.
이 부등호 사이사이에 0부터 9까지의 숫자 중 중복 없이 하나씩 넣어서, 모든 부등호 관계를 만족하는 수열을 만드는 것이 문제의 핵심이다.

만약 그런 수열이 여러 개 존재한다면, 그 중에서 가장 큰 수와 가장 작은 수를 각각 출력해야 한다.

 

예제 입력 1을 예시로 들어보자

2 
< >

부등호가 두 개이므로, 총 숫자 3개가 필요하다.
예를 들어 2 < 5 > 4, 8 < 9 > 7, 0 < 2 > 1, 0 < 4 > 2 등 다양한 수열이 가능하다.

이 중 숫자를 이어붙여서 수를 만들었을 때:

• 가장 큰 수는 8 < 9 > 7 → 897
• 가장 작은 수는 0 < 2 > 1 → 021

따라서 출력은 다음과 같은 것이다.

 

897
021

 

 

 

구현 방향:

이 문제를 해결하기 위해 가장 먼저 떠오른 방법은 브루트포스(완전 탐색)와 백트래킹이다.

전체적인 아이디어는 다음과 같다:

• 숫자는 0부터 9까지 중복 없이 한 번씩만 사용 가능하므로, 가능한 모든 숫자 조합을 시도해보는 방식이 유효하다.
• 맨 앞자리 숫자부터 시작하여, 재귀적으로 다음 자리에 들어갈 숫자를 선택한다.
• 이때, 선택한 숫자와 다음 숫자 사이의 부등호 관계가 성립하는 경우에만 재귀 호출을 진행한다.
• 만약 주어진 부등호 조건을 모두 만족하는 수열이 만들어졌다면, 그 수열을 하나의 수로 간주해 저장한다.
• 이렇게 모든 가능한 수를 탐색한 후, 만들어진 수들 중에서 최댓값과 최솟값을 각각 출력한다.

이 과정에서 조건을 만족하지 않거나, 이미 사용한 숫자를 또 쓰려고 하면 백트래킹하여 이전 상태로 돌아간다.
이를 통해 모든 가능한 경우를 빠짐없이 탐색하면서도, 불필요한 연산은 줄일 수 있다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답 코드:

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 k;
    static char[] us; //부등호 담을 배열
    static int [] number;//숫자를 담을 배열
    static boolean [] visited=new boolean[10]; //사용한 숫자
    static List<String> resultList=new ArrayList<>();
    static long min = Long.MAX_VALUE;
    static long max = Long.MIN_VALUE;

    //등호 비교
    public static boolean compare(int num1, char c, int num2){
        if(c=='<') return num1 < num2;
        else return num1 > num2;
    }

    public static void dfs(int num,int index,StringBuilder result){

        //모두 탐색 되었다면
        if(index==us.length){
            resultList.add(String.valueOf(result));
            return;
        }

        char c=us[index];

        for(int i=0; i<10; i++){
            if(!visited[i] && compare(num,c,i) ){
                visited[i]=true;
                result.append(i);
                dfs(i,index+1,result);
                //백트레킹
                result.deleteCharAt(result.length()-1);
                visited[i]=false;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        k=Integer.parseInt(st.nextToken());
        us=new char[k];
        number=new int[k+1];

        //부등호 저장
        StringTokenizer st1=new StringTokenizer(br.readLine());
        for(int i=0; i<k; i++){
            us[i] = st1.nextToken().charAt(0);
        }
        //초기세팅 끝

        //탐색 시작
        for(int i=0; i<10; i++){
            visited=new boolean[10];
            visited[i]=true;
            dfs(i,0, new StringBuilder(String.valueOf(i)));
        }

        //최대 최소 구하기
        min= Long.parseLong(resultList.get(0));
        max= Long.parseLong(resultList.get(resultList.size()-1));

        //결과 출력
        System.out.println(max);

        StringBuilder minStr= new StringBuilder(String.valueOf(min));
        if(minStr.length()!=k+1){
            minStr.insert(0,"0");
        }
        System.out.println(minStr);

    }
}

 

 

코드 흐름 예시:

k = 3  
부등호: < > <

DFS(0, 0, "0")  
 ├─ 1 선택 → DFS(1, 1, "01")  
 │    └─ 다음 후보 없음 → 종료 후 백트래킹  
 ├─ 2 선택 → DFS(2, 1, "02")  
 │    ├─ 1 선택 → DFS(1, 2, "021")  
 │    │    ├─ 3 선택 → DFS(3, 3, "0213") → 완료 → 백트래킹  
 │    │    ├─ 4 선택 → DFS(4, 3, "0214") → 완료 → 백트래킹  
 │    │    └─ ... 다음 후보 계속 탐색 → 백트래킹  
 │    ├─ 0 선택 → 불가 (이미 방문)  
 │    └─ 기타 후보 탐색 → 조건에 맞으면 재귀 → 백트래킹  
 ├─ 3 선택 → DFS(3, 1, "03")  
 │    ├─ 1 선택 → DFS(1, 2, "031")  
 │    │    ├─ 2 선택 → DFS(2, 3, "0312") → 완료 → 백트래킹  
 │    │    └─ ... 다음 후보 탐색 → 백트래킹  
 │    └─ 기타 후보 탐색 → 조건 맞으면 재귀 → 백트래킹  
 └─ ... 다음 숫자 후보 탐색

 

 

마무리하며:

이 문제는 문제 이해 자체가 어렵지 않으며, 백트래킹과 브루트포스 알고리즘 구현 연습에 매우 적합한 문제라고 생각한다.
직접 문제를 풀면서 재귀 호출의 흐름을 따라가 보고, 백트래킹 과정을 체험해보면 재귀 방식에 대한 이해가 더욱 깊어질 것이다.
따라서 이 문제는 재귀와 백트래킹을 익히고자 하는 분들에게 좋은 연습 문제가 될 것이다.

 

 

감사합니다.