2529: 부등호

• 모든 수의 조합을 순회해서 len(visit) == k+1일 때 유효성을 검사하면 당연히 시간 초과가 발생함 (10의 10승)
• 따라서 depth 마다 확인 작업이 필요함
• 이를 위해선 dfs()에서 인자로 현재 depth와, 이전 숫자 (before_number)를 넘겨주어야함
• 1) depth가 0인 경우에는 부등호와 관계 없이 숫자를 넣어줘야함
• 2) 그 외의 경우에는 부등호 관계가 유효한지 검사해줘야함

import sys

k = int(input())
A = list(sys.stdin.readline()[:-1].split(' '))
visit = []

max_value = 0; min_value = 10 ** (k+1)
def dfs(depth, before_number):
    global max_value
    global min_value
    if depth == k+1:
        num = ""
        for x in range(k+1):
            num += str(visit[x])
        num = int(num)
        max_value = max(max_value, num)
        min_value = min(min_value, num)
        return
    for i in range(10):
        if i not in visit:
            if depth == 0:
                visit.append(i)
                dfs(depth+1, i)
                visit.pop()
            elif (A[depth-1] == '<' and before_number < i) or (A[depth-1] == '>' and before_number > i):
                visit.append(i)
                dfs(depth+1, i)
                visit.pop() 

dfs(0, None)
if len(str(max_value)) != k+1:
    max_value = "0" + str(max_value)
if len(str(min_value)) != k+1:
    min_value = "0" + str(min_value)
print(max_value); print(min_value)