[알고리즘] 백준 2529 부등호 / python

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

2529번: 부등호

 

#순열이 오름차순일때 사용하는 함수
def next_permu(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1
    
    a[i-1], a[j] = a[j], a[i-1]

    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    
    return True

#순열이 내림차순일때 사용하는 함수
def prev_permu(a):
    i = len(a)-1
    while i > 0 and a[i-1] <= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] >= a[i-1]:
        j -= 1
    
    a[i-1], a[j] = a[j], a[i-1]

    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    
    return True

#부등호를 만족하는지 확인하는 함수
def check(permu, a):
    for i in range(len(a)):
        if a[i] == '<' and permu[i] > permu[i+1]:
            return False
        if a[i] == '>' and permu[i] < permu[i+1]:
            return False
    return True

k = int(input())
a = input().split()
small = [i for i in range(k+1)]
big = [(9-i) for i in range(k+1)]

#부등호를 만족하지 못한다면, 다음 순열을 구해서 다시 확인한다
#순열이 끝이라면 next_permu함수는 True를 리턴한다
while True:
    if check(small, a):
        break
    if not next_permu(small):
        break
#부등호를 만족하지 못한다면, 다음 순열을 구해서 다시 확인한다
#순열이 끝이라면 prev_permu함수는 True를 리턴한다
while True:
    if check(big, a):
        break
    if not prev_permu(big):
        break

print(''.join(map(str, big)))
print(''.join(map(str, small)))