[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개 나열된 순서열 A가 존재
• 부등호 기호 앞뒤에 넣을 수 있는 숫자는 중복되지 않는 숫자로 0부터 9까지의 정수이다.
• 부등호를 제거한 숫자 중 가장 큰 숫자와 가장 작은 숫자를 출력
• 부등호는 k개, 숫자는 k+1개
• 위의 조건에 맞는 모든 경우의 수를 다 탐색

문제 풀이

재귀적으로 접근하였다. 각 분기는 그 숫자를 선택하느냐 안하느냐로 나뉘게 된다.
먼저 종료 조건을 세웠다.
종료 조건 : 부등호를 제외한 길이가 k+1인가? 그렇다면 종료 후 최대값과 최소값 갱신

다음은 재귀를 실행시키는 조건을 세웠다.
주어진 조건1. 0~9사이의 숫자인가?
주어진 조건1. 이미 방문한 숫자가 아닌가?
주어진 조건2. 부등호에 들어갈 수 있는가?

# 재귀함수
def make_inequality_signs_num(n, current, visited, inequality_signs, max_num, min_num):
    # 비교 후 조건에 맞고 가장 작거나 크다면 기존 값을 업데이트 
    # 종료조건은 현재 길이가 n이 된다면 종료
    # n의 역할 : 만들어야 하는 길이(부등호 개수가 k라면 n은 K+1임)
    # current의 역할 : 현재 부등호에 맞게 만들어진 문자열
    # visited의 역할 : 방문한 숫자(0~9)
    # inequality_signs : 방문해야할 부등호 리스트
    length = len(current)
    if length == n: # 종료 조건
        num = int(current)
        max_num = max(max_num, num) # 최대값 갱신
        min_num = min(min_num, num) # 최소값 갱신
        return max_num, min_num
    for i in range(10):
        if i not in visited : # 0~9사이이고 중복되지 않는 숫자라면
            visited.append(i)
            if length > 0: # 시작 문자열이 ''이기에 length-1 인덱싱을 위해 조건 추가
            	# 부등호가 '<'이고 부등호 앞뒤 숫자가 조건에 부합한다면
                if inequality_signs[length-1] == '<' and int(current[-1]) < i:
                    max_num, min_num = make_inequality_signs_num(n, current+str(i), visited, inequality_signs, max_num, min_num)
				# 부등호가 '>'이고 부등호 앞뒤 숫자가 조건에 부합한다면
                elif inequality_signs[length-1] == '>' and int(current[-1]) > i: # '>' 인 경우
                    max_num, min_num = make_inequality_signs_num(n, current+str(i), visited, inequality_signs, max_num, min_num)
            else :
                # current가 비어 있을 때는 부등호 검사 없이 숫자 추가
                max_num, min_num = make_inequality_signs_num(n, current + str(i), visited, inequality_signs, max_num, min_num)
            visited.pop()  # 마지막에 추가된 숫자를 제거(현재 숫자를 넣지 않는 경우와 넣는 경우 두가지 경우로 나뉘기에)
    return max_num, min_num

k = int(input()) # 부등호의 개수
inequality_signs = input().split() # 부등호 리스트
# 재귀함수 시작 
max_num, min_num = make_inequality_signs_num(k+1, '', [], inequality_signs, 0, float('inf'))
max_num = str(max_num)
min_num = str(min_num)

# 첫숫자가 0인경우는 형변환시 사라지기에 예외케이스 처리
if len(max_num) == k:
    max_num = '0'+max_num
if len(min_num) == k:
    min_num = '0'+min_num

# 답 출력
print(max_num)
print(min_num)

풀면서 어려웠던 점

1. current 설정이 어려웠다. 재귀함수의 if length > 0를 생각나지 않았다.
2. visited.pop()을 어디서 해야할지 헷갈렸다. 처음에는 각 조건 안에 넣었었는데 후에 변경하였다.