[백준] 2529. 부등호 (JAVA)

이번에 풀어 볼 문제는 < 백준 2529번. 부등호 > 이다.

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

📌 문제 탐색하기

목표

k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값 찾기

해야 할 것

1. 모든 조건을 만족하는 정수들을 어떻게 찾을까?
2. 시간복잡도 고려하기
3. 최대값과 최솟값을 어떻게 구할까?

입력

[첫 줄] 부등호 문자의 개수 : k ( 2 ≤ k ≤ 9 )

[둘째 줄] k개의 부등호 기호

아이디어

1. 모든 조건을 만족하는 정수들을 어떻게 찾을까?

 

일단 주어진 부등호의 개수가 k개일 때, 우리가 채워야 할 숫자들은 모두 k+1개이다.

그럼 각 자리마다 0~9까지의 숫자를 하나씩 넣어볼 수 있을텐데, 이때 그냥 넣는 것이 아니라 다음 2가지 조건을 검증하며 진행해야 한다.

1) 이전에 사용된 숫자인가?

2) 주어진 부등호 순서를 만족하는가?

 

예를 들어, 첫 번째 자리에 숫자 0을 넣었다고 가정해보자.

그럼 다음 자리에는 같은 숫자 0을 다시 사용할 수 없다. 여기서 숫자의 방문 여부를 기록할 배열이 필요하다는 아이디어를 얻을 수 있다.

 

또 만약 첫 번째 부등호가 '>' 라면, 첫번째 자리에 숫자 0이 오면 이후 어떤 숫자를 넣더라도 조건을 만족할 수 없다. 따라서 첫 번째 자리에 0이 오는 경우는 이후에 어떤 경우의 수가 가능한지 고려할 필요없이, 바로 탐색을 중단하고 다음 숫자(1) 이 오는 경우로 넘어가는 것이 효율적이다.

 

즉, 이 문제는 숫자를 선택하고, 조건을 확인한 뒤, 조건을 만족하면 계속해서 탐색을 진행하고 만족하지 못하면 다음 숫자로 넘어가는 "백트래킹" 방법으로 풀이할 수 있다.

 

 

2. 시간복잡도 고려하기

 

백트래킹은 근본적으로 가능한 모든 경우를 탐색하는 알고리즘이다.

k의 최대값은 9이므로, 최악의 경우 총 k+1 자리의 숫자를 만들어야 한다.

즉, 최악의 경우 전체 연산횟수는 10!이 되는데, 이는 3628800 으로 시간제한 안에 해결 가능한 연산횟수이다.

또한 조건을 만족하지 않는 경우는 탐색을 일찍 종료하기 때문에 실제 연산 횟수는 이보다 적을 것으로 생각된다.

 

3. 최대값과 최소값을 어떻게 구할까?

이 문제는 최대값과 최소값을 모두 출력해야 한다.

특히 최소값의 경우는 첫 자리가 0인 경우도 출력해야 한다. 따라서 숫자들을 문자열로 저장하고 출력하는 것이 편할 것으로 예상된다.

 

결과들을 문자열로 저장할 리스트를 만들고 이 리스트를 오름차순 정렬하면, 첫번째 오는 원소가 최소값, 제일 마지막에 오는 원소가 최대값이 될 것이다.

📌 코드 설계하기

 

1. Input 처리: k와 부등호 조건(operators)을 입력받는다.

2. 숫자의 방문 여부를 기록하는 visited 배열, 결과를 저장할 results 리스트를 정의한다.

3. 백트래킹 함수 구현 : 조건을 만족하지 않으면 탐색 중단하도록 구현

4. 부등호 검증 함수 구현: 이전 숫자와 현재 숫자 사이의 부등호 조건을 확인.

5.결과 리스트를 정렬하여 최대값과 최소값을 출력.

 

 

📌 정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;


public class Main{
    static int k;
    static String[] operators;
    static boolean[] visited = new boolean[10];
    static ArrayList<String> results = new ArrayList<>();

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

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

        backtrack("",0);
        Collections.sort(results); //

        System.out.println(results.get(results.size()-1)); // 최대값
        System.out.println(results.get(0)); // 최소값
    }

    //backtracking 함수 구현
    static void backtrack(String num, int depth){
        if(depth == k+1){
            results.add(num);
            return;
        }

        for(int curNum = 0; curNum < 10; curNum++){
            if(!visited[curNum]){
                if (depth == 0) {
                    visited[curNum] = true; // 현재 숫자를 선택하고 방문한 걸로 표시
                    backtrack(num+curNum, depth+1); // 현재 숫자를 선택했을 때 -> 다음 숫자 선택 과정 진행
                    visited[curNum] = false; // 탐색이 끝났으므로 다음 탐색 때는 다시 이 숫자를 사용할 수 있도록 복구

                }else{
                    int preNum = num.charAt(depth-1)-'0';
                    String curOperator = operators[depth-1];
                    if(isValid(preNum,curNum,curOperator)){
                        visited[curNum] = true; // 현재 숫자를 선택하고 방문한 걸로 표시
                        backtrack(num+curNum, depth+1); // 현재 숫자를 선택했을 때 -> 다음 숫자 선택 과정 진행
                        visited[curNum] = false; // 탐색이 끝났으므로 다음 탐색 때는 다시 이 숫자를 사용할 수 있도록 복구
                    }
                }
            }
        }
    }
    //부등호 검증 함수 구현
    static boolean isValid(int preNum, int curNum, String curOperator){
        if(curOperator.equals("<")){
            return preNum < curNum ;
        }else{
            return preNum > curNum ;
        }
    }
}

📌 알게 된 것

백트래킹의 기본 구조는

탐색 ➡️ 조건 확인 ➡️ 되돌아가기 과정을 반복하는 것이다.

 

위와 같이 방문 배열을 활용할 때는 '되돌아가기' 과정에서 특정 단계에서 탐색을 마친 뒤, visited 배열을 반드시 원래 상태로 복구해놓는 과정이 필요하다!

visited[curNum] = true; // 현재 숫자를 선택하고 방문한 걸로 표시
backtrack(num+curNum, depth+1); // 현재 숫자를 선택했을 때 -> 다음 숫자 선택 과정 진행
visited[curNum] = false; // 탐색이 끝났으므로 다음 탐색 때는 다시 이 숫자를 사용할 수 있도록 복구