[백준/Python3] 2529번: 부등호

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

 

 

 

문제

 

풀이

import sys
import itertools

def check(array, ptr):
    global n
    for i in range(n):
        if array[i] == '>' and not ptr[i] > ptr[i + 1]:
            return False
        elif array[i] == '<' and not ptr[i] < ptr[i + 1]:
            return False
    return True

num = [str(x) for x in range(10)]
n = int(sys.stdin.readline())
array = list(map(str, sys.stdin.readline().split()))


max_ptr = None
min_ptr = None
for i in (itertools.permutations(num, n + 1)):
    if check(array, i):
        min_ptr = i
        break

for perm in itertools.permutations(reversed(num), n + 1):
    if check(array, perm):
        max_ptr = perm
        break
print(''.join(max_ptr))
print(''.join(min_ptr))

 

모든 조합의 경우를 check라는 검증 함수를 통해 필요한 부분만 값을 받아올 수 있도록 작성했다. 역순 순열을 통해 모든 순회를 통해 검증하는 것이 아닌 Max 값과 min 값을 각각 따로 받아 값을 받아 최적화를 진행했다.