문제

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

나의 코드

"""

"""

from sys import stdin
input = stdin.readline

k = int(input())
operator = list(input().split())
num = [ x for x in range(10) ]
visited = [False] * 10
num_list = [] # 숫자 조합 리스트
tmp = []
min_answer, max_answer = 1e11, 0

def backtrack(dep): # 백트래킹을 통해 모든 경우의 대한 숫자의 조합을 구함

    if dep == k+1: # 만약 모든 숫자가 다 써진다면 숫자 조합 리스트에 넣음
        num_list.append(''.join(map(str, tmp)))
        return

    for i in range(10):
        if not visited[i]:
            visited[i] = True
            tmp.append(i)
            backtrack(dep+1)
            visited[i] = False
            tmp.pop()

backtrack(0)

for num in num_list: # 부등호와 숫자와의 관계가 성립하면 정답을 업데이트함
    for idx in range(k):
        if operator[idx] == '<' and num[idx] > num[idx+1]:
            break
        elif operator[idx] == '>' and num[idx] < num[idx+1]:
            break
    else:
        max_answer = max(max_answer, int(num))
        min_answer = min(min_answer, int(num))

print(str(max_answer).zfill(k+1))
print(str(min_answer).zfill(k+1)) # '021'의 경우 위에서 int()로 변환시 '21'이 되기 때문에 다시 문자열로 바꾸어 zfill()함수를 통해 0을 채워준다.

    

다른 풀이 코드

"""

"""

from sys import stdin
input = stdin.readline

k = int(input())
operator = list(input().split())
visited = [False] * 10
min_answer, max_answer = '', ''

def check(i, j, ope):
    if ope == '>':
        return i > j
    else:
        return i < j

def backtrack(dep, s):
    global min_answer, max_answer

    if dep == k+1:
        if len(min_answer) == 0: # 처음 이 깊이까지 오는 수는 최솟값일 수 밖에 없다(0부터 백트래킹을 시작하기 때문에)
            min_answer = s
        else:
            max_answer = s
        return

    for i in range(10):
        if not visited[i]:
            if dep == 0 or check(s[-1], str(i), operator[dep-1]): # 제일 처음 수 이거나 부등호 조건에 맞는 수 일때 통과
                visited[i] = True
                backtrack(dep+1, s+str(i))
                visited[i] = False

backtrack(0, '')
print(max_answer)
print(min_answer)

    

설명

백트래킹(완전탐색)을 활용한 문제, 연산자 끼워넣기 문제의 반대?

참고 자료