[백준/Python] 2529_부등호

문제

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

2529번: 부등호

풀이

처음에는 itertools.permutations로 풀려고 했으나 한번에 모든 경우의 수를 배열에 담기 때문에 메모리 초과가 났습니다.

따라서 재귀를 이용해서 완전 탐색하여 풀었습니다.

매자릿수 마다 0 ~ 9까지 숫자를 순회하여 한 숫자씩 string 타입으로 붙여나갔기 때문에, 맨 처음 나온 수가 최소값이 되고 맨 마지막에 나온 수가 최대값이 됩니다.

check 배열로 숫자의 중복을 막았습니다.

코드

import sys


def is_possible(i, j, k):
    if k == '<':
        return i < j
    if k == '>':
        return i > j
    return True


def recursive(cnt, num):
    global min_num, max_num
    if cnt > n:
        if not len(min_num):
            min_num = num
        else:
            max_num = num
        return
    for i in range(10):
        if not check[i]:
            if cnt == 0 or is_possible(num[-1], str(i), brackets[cnt - 1]):
                check[i] = True
                recursive(cnt + 1, num + str(i))
                check[i] = False


n = int(sys.stdin.readline().rstrip())
brackets = sys.stdin.readline().rstrip().split()
check = [False] * 10
max_num, min_num = '', ''
recursive(0, '')
print(max_num)
print(min_num)