[Python - 백준 2529] 부등호

2529번: 부등호

문제 설명

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력형식

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력형식

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

입출력 예시

풀이 과정

부등호 갯수를 n개라고 할 때, 0~9 에서 n+1만큼 숫자를 고르는 문제였다. visited를 이용하여 '000'같은 중복을 피했고, possible 함수를 이용하여 부등호가 옳을 때만 다음 backtracking을 실행하도록 구현했다. 처음에는 임시 리스트에 선택된 숫자를 넣은 다음에 부등호를 판별하여 min값과 max값을 넣어주는 식으로 구현했는데, 시간초과가 발생했다.

또한 021같은 경우는 21이아니라 021로 출력해줘야하므로 선택된 값들을 int로 하는것보다 string으로 바로 추가해주어야 했다.

+) min값과 max값을 구할 때는 어짜피 브루트포스로 순차적으로 조합을 구하기때문에 min_value값은 맨처음 통과한 값으로, max_value는 계속 값을 넣어주면서 구하면 쉽게 구할 수 있다 : )

def possible(item1, item2, symbol):
    if symbol == '<':
        return item1 < item2
    if symbol == '>':
        return item1 > item2


def backtracking(idx, string):
    global min_value
    global visited
    global max_value
    if idx == n + 1:
        if not len(min_value):
            min_value = string
        else:
            max_value = string
        return
    for i in range(10):
        if visited[i]:
            continue
        if idx == 0 or possible(string[-1], str(i), stack[idx - 1]):
            visited[i] = True
            backtracking(idx + 1, string + str(i))
            visited[i] = False


if __name__ == '__main__':
    n = int(input())
    stack = list(input().split())
    max_value = ''
    min_value = ''
    visited = [False] * 10
    backtracking(0, '')
    print(max_value)
    print(min_value)