[BOJ] 부등호

---

코드

import sys
# from collections import deque
input = sys.stdin.readline

# 백트래킹으로 각 숫자가 0~9중 하나인 (k+1)자리 수 구하기 (각 자리의 수는 중복 X)
def dfs():
    if len(arr) == k+1:
        if validate(arr):
            comp(arr)
        return

    for i in range(10):
        if i not in arr:
            arr.append(i)
            dfs()
            arr.pop()

# 조건 만족 여부 판단
def validate(arr):
    for i in range(k):
        operator = ops[i]
        if operator == '>' and arr[i] < arr[i+1]: return False
        if operator == '<' and arr[i] > arr[i+1]: return False

    return True

# 최대/최소 여부 판단
def comp(arr):
    global minV, maxV
    
    num = int(''.join(map(str, arr)))
    if num > maxV: maxV = num
    if num < minV: minV = num
    return
        
        
k = int(input())
ops = input().split()    # 부등호 리스트
arr = []    # k+1자리 수
minV = sys.maxsize
maxV = 0

dfs()
print(f'{maxV:0{k+1}}')
print(f'{minV:0{k+1}}')

결과

풀이 방법

• 각 자리 수가 모두 다르기 때문에 최대 10자리의 수이지만 조건에 맞는지 테스트해야 하는 수는 총 10! = 3628800 개이다.
• 최대 10자리 수 사이의 각 부등호가 올바른지 판단하기 위해서 최대 9번의 계산이 필요할 것이다.
• 따라서 최대 연산횟수는 10! * 9 이므로 브루트포스로 풀어도 제한시간을 넘지 않을 것이다.
• 테스트해야 하는 수는 백트래킹으로 구하였다. 각 자리의 수가 중복되지 않는 K자리 수의 가짓수를 구하는 문제와 같다 (N과 M 문제)
• 백트래킹하다가 k+1 자리 수가 만들어졌으면 해당 수 사이에 부등호를 넣었을 때 조건을 만족하는지 판단하고, 만족한다면 최대/최소값인지도 판단하여 갱신한다.
• ans가 k 자리 수가 아닌 경우 숫자 앞에 0을 채우는 방법: print(f'ans:0{k}'})

---