[Algorithm] 99클럽 코테 스터디 13일차 TIL | 백준_부등호(2529번)

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

---

역대급 오래 걸린 문제🤦‍♀️

3년 전에 내가 푼 풀이를 참고하여 겨우 정답을 맞혔다

 

"<" 부호가 올 때는 현재 수보다 무조건 큰 값이 오고

">"부호가 올 때는 현재 수보다 무조건 작은 값이 오는 게 핵심이다!!

 

현재수를 current, 정답을 각 자리 수마다 넣어줄 배열 (arr)의 현재 인덱스를 index로 사용해 줄 것이다.

 

current = 0, index = 1 (부등호 배열과 함께 쓰기 위해 1부터 시작)부터 시작한다.

이때, arr [0] = current로 초기화해 준다.

 

부등호가 "<"라면

현재 수 보다 큰 1부터 9까지 arr [1]에 들어갈 수 있고

재귀로 dfs(1,2) 이렇게 다음 경우의 수를 호출한다.

백트래킹을 해서 모든 경우의 수를 찾아야 하므로 재귀 호출 후 방문 배열을 다시 false로 바꿔준다.

if("<".equals(sign[index-1])){
    for(int i = current+1; i <= 9; i++){
        if(!visited[i]){
            visited[i] = true;
            arr[index] = i;
            dfs(i,index+1);
            visited[i] = false;
        }
    }
}

 

부등호가 ">"라면

현재 수(2) 보다 작은 1부터 0까지 arr [2]에 들어갈 수 있다.

(현재 수가 1일 때는(dfs(1,2)) 반복문 조건에 맞지 않으므로 현재 호출된 dfs() 종료 -> 이전 스택 프레임으로 돌아감 -> 호출 지점으로 돌아가 visited [1] = false 되고 dfs(2,2)를 호출할 거임 :백트래킹)

else if(">".equals(sign[index-1])){
    for(int i = current-1; i >= 0; i--){
        if(!visited[i]){
            visited[i] = true;
            arr[index] = i;
            dfs(i, index+1);
            visited[i] = false;
        }
    }
}

 

이런 식으로 반복하다 보면 index값이 k+1 값과 같아지는 순간이 오는데

이때 arr 배열의 숫자들을 합치고 재귀를 빠져나와야 한다.

(index는 애초에 arr을 위한 index인데, arr 길이가 k+1이기 때문에!)

if(index == k+1){
    StringBuilder sb = new StringBuilder();
    for(int n : arr){
        sb.append(n);
    }
    min = Math.min(min, Long.parseLong(sb.toString()));
    max = Math.max(max, Long.parseLong(sb.toString()));
    return;
}

 

전체코드

import java.util.*;
import java.io.*;
class Main{
    static boolean[] visited;
    static int[] arr;
    static String[] sign;
    static int k;
    static long min = Long.MAX_VALUE, max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        sign = new String[k];

        for(int i = 0; i < k; i++){
            sign[i] = st.nextToken();
        }

        arr = new int[k+1];
        for(int i = 0; i <= 9; i++){
            visited = new boolean[10];
            arr[0] = i;
            visited[i] = true;
            dfs(i, 1);
        }
        System.out.println(max);
        System.out.println(String.valueOf(min).length() == k ? "0"+min : min);
    }
    public static void dfs(int current, int index){
        if(index == k+1){
            StringBuilder sb = new StringBuilder();
            for(int n : arr){
                sb.append(n);
            }
            min = Math.min(min, Long.parseLong(sb.toString()));
            max = Math.max(max, Long.parseLong(sb.toString()));
            return;
        }
        if("<".equals(sign[index-1])){
            for(int i = current+1; i <= 9; i++){
                if(!visited[i]){
                    visited[i] = true;
                    arr[index] = i;
                    dfs(i,index+1);
                    visited[i] = false;
                }
            }
        }else if(">".equals(sign[index-1])){
            for(int i = current-1; i >= 0; i--){
                if(!visited[i]){
                    visited[i] = true;
                    arr[index] = i;
                    dfs(i, index+1);
                    visited[i] = false;
                }
            }
        }
    }
}

 

 

후기: 문제 보면 풀이가 자동으로 떠오르는 뇌 갖고싶다ㅎㅎㅎ