BOJ : 2529 부등호

0-9 사이의 값을 가지는 순열 중 해당 부등호 조건을 만족시키는 최솟값과 최댓값을 출력하는 알고리즘.
check 함수는 입력받은 string 이 현재시점까지 부등호 조건을 만족시키는 지를 확인한다.

perform 순열을 만든다. 부등호조건을 만족시키지 않으면 더이상 순열을 만들지 않고 중지한다. length 가 원하는 len이 되었으면 해당 값을 max, min 값과 비교한다.

import sys
input = sys.stdin.readline

nums = '0123456789'
k = int(input())
ls = input().strip().split()

max = '000'
min = '999'

def permutation():
    size = k + 1

    def check(s):
        for i in range(0, len(s) - 1):
            if ls[i] == '>' and s[i] < s[i + 1]:
                return False
            elif ls[i] == '<' and s[i] > s[i + 1]:
                return False
        return True

    def perform(cur_arr, visited):
        if len(cur_arr) == size:
            global max, min
            # print('cur_arr = {}, max = {}, min = {}'.format(cur_arr, max, min))
            if check(cur_arr):
                if cur_arr > max:
                    max = cur_arr
                if cur_arr < min:
                    min = cur_arr
            return
        if not check(cur_arr):
            return
        for i in range(len(nums)):
            if not visited[i]:
                visited[i] = True
                perform(cur_arr + nums[i], visited)
                visited[i] = False

    visited = [False for _ in range(len(nums))]
    perform('', visited)

permutation()
print(max)
print(min)