[백준 2529번] 부등호

2529번: 부등호

import copy

k = int(input())

signs = list(input().split())

minimum, maximum = float("inf"), float("-inf")

def dfs(numbers,num_set):

    global minimum, maximum, minimum_string, maximum_string

    length = len(numbers)
    
    if length == k+1: # 숫자의 개수가 k+1를 만족할 경우 함수 종료
        final_value = int("".join(list(map(str,numbers))))
        if final_value < minimum:
            minimum = final_value
            minimum_string = "".join(list(map(str,numbers)))
        if final_value > maximum:
            maximum = final_value
            maximum_string = "".join(list(map(str,numbers)))
        return
    
    for num in num_set:
        
        if length == 0: # 첫번째 원소인 경우
            new_set = copy.deepcopy(num_set)
            new_set.discard(num)
            dfs(numbers+[num],new_set)

        else: # 부등호에 따라 다르게 탐색
            if signs[length-1] == '<' and numbers[length-1] < num:
                new_set = copy.deepcopy(num_set)
                new_set.discard(num)
                dfs(numbers+[num], new_set)
            elif signs[length-1] == '>' and numbers[length-1] > num:
                new_set = copy.deepcopy(num_set)
                new_set.discard(num)
                dfs(numbers+[num], new_set)

dfs([], set([0,1,2,3,4,5,6,7,8,9])) 

print(maximum_string)
print(minimum_string)

 

이번 문제는 k개의 부등호가 있을 때, 각 부등호와 숫자 사이의 관계가 만족하도록 하는 k+1개의 숫자 중 최댓값과 최솟값을 구하는 '완전 탐색(Brute-Force)' 문제이다.

 

dfs 함수를 선언한 뒤, 먼저 종료 조건인 k+1개의 숫자가 주어진 경우 최댓값과 최솟값을 업데이트 해주는 방식으로 코드를 작성하였다. 그 외에는 부등호의 관계에 따라 DFS 함수를 호출하여 모든 경우의 수를 탐색하도록 하였다.

 

완전 탐색을 연습해볼 수 있었던 문제였다 :)