백준 2529번. 부등호 (Python / 파이썬)

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

---

문제 풀이 

부등호를 만족시키는 모든 수를 찾기 위해서는 하나씩 숫자를 넣어보며 부등호를 만족시키는지 확인해야 한다. 

위의 그림처럼 부등호 사이사이에 문자열이 들어가게 되는데 그 문자열의 index와 부등호의 index가 존재한다.

따라서 이 index 정보와 부등호를 만족시키는 k+1 자리수의 숫자 문자열을 완성시키기 위해 빈 문자열을 넘겨주어

브루트포스 알고리즘을 활용하였다. 

 

0~9 까지의 숫자를 부등호 사이사이에 넣을 수 있으므로 for문을 활용하여 숫자를 하나씩 넣어본다. 

이때, 주의해야할 점은 선택된 숫자는 모두 달라야하므로 check 배열을 만들어 이미 사용된 숫자인지를 체크해준다. 

만약 사용되지 않은 숫자라면 부등호를 만족하는지 확인한다. 

이때, index가 0이라면 비교할 필요가 없으므로 그냥 문자열에 넣어준다. 

 

만약 이러한 조건을 모두 만족한다면 check 배열을 True로 만들어주고 

index + 1 과 기존 문자열에 현재 숫자를 추가하여 다시 dfs함수로 넘겨준다. 

이때, 꼭! check 배열을 다시 False로 만들어주어야 한다. 

 

이렇게 탐색을 진행하다가 문자열의 길이가 k+1이 되면 배열에 문자열을 넣어주고 종료한다. 

이 과정을 계속 반복하면 배열에는 부등호를 만족하는 문자열들만이 남게된다. 

따라서 이 배열을 오름차순으로 정렬해준뒤 맨 앞, 맨 뒤 값으로 최소, 최대 값을 찾을 수 있다. 

---

My Code 

def get_num(x, y, oper):
    if oper == '<':
        if x > y : 
            return False 
    else:
        if x < y:
            return False 
    return True 

def dfs(idx, num):
    if idx == k+1:
        ans.append(num)
        return

    for i in range(10):
        if not check[i]:
            if idx == 0 or get_num(num[idx-1], str(i), oper[idx-1]):
                check[i] = True 
                dfs(idx + 1, num + str(i))
                check[i] = False 

k = int(input())
oper = list(input().split())

check = [False] * 10
ans = []
dfs(0, '')

ans.sort()
print(ans[-1])
print(ans[0])