[백준 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

---

접근

K개의 부등호가 있다면 숫자는 K+1개의 숫자이다. 

이전의 숫자와 비교를 해야하기 위해 현재까지 선택한 숫자의 개수와 현재 부등호를 가리킬 picked를 사용한다.

현재 picked가 1이라면 numbers에 인덱스 1에 있는 수와 부등호 리스트에 1에 있는 부등호를 사용하여 비교할 수를 찾는다. 

찾았다면 picked를 증가시켜 다음으로 넘어간다. 그렇다면 picked는 이전의 수를 가리키게 되고 동시에 현재 부등호를 가리킬 수 있다.

마지막으로 picked가 N이 되었을 때 최솟값 최댓값 비교를 한다.

 

구현

- 처음에 0부터 9까지의 수를 dfs에 전달하여 탐색을 진행한다.

- 이때 중복된 수는 나올 수 없기 때문에 이미 선택한 수를 표시할 visited을 만들었다.

for n in range(10):
    visited[n] = 1
    numbers.append(n)
    dfs(0, numbers)
    visited[n] = 0
    numbers.pop()

 

- picked가 N이라면 N개의 부등호를 모두 사용한 것이다. 따라서 최댓값과 최솟값을 구한다.

- 현재 max_ans와 min_ans에는 문자열로된 숫자가 저장되어 있다. 왜냐하면 예시 출력처럼 021이 출력되어야하기 때문이다.

- 비교할 떄는 두 수를 int형으로 변환하여 비교한다.

- 그리고 현재 부등호가 '>'일 떄와 '<'로 나누어서 구한다.

- 0부터 9까지 탐색하여 picked가 가리키는(이전의 수) 숫자와 비교하여 다음으로 진행한다.

- 이때 선택한 숫자는 표시한다.

def dfs(picked, numbers):
    global visited, max_ans, min_ans

    if picked == N:
        number = ''.join(map(str, numbers))
        if int(max_ans) < int(number):
            max_ans = number
        if int(min_ans) > int(number):
            min_ans = number
        return

    if sign_list[picked] == '>':

        for n in range(10):
            if numbers[picked] > n and visited[n] == 0:
                numbers.append(n)
                visited[n] = 1
                dfs(picked+1, numbers)
                numbers.pop()
                visited[n] = 0
    elif sign_list[picked] == '<':

        for n in range(10):
            if numbers[picked] < n and visited[n] == 0:
                numbers.append(n)
                visited[n] = 1
                dfs(picked+1, numbers)
                numbers.pop()
                visited[n] = 0

---

전체 코드

import sys
input = sys.stdin.readline

def dfs(picked, numbers):
    global visited, max_ans, min_ans

    if picked == N:
        number = ''.join(map(str, numbers))
        if int(max_ans) < int(number):
            max_ans = number
        if int(min_ans) > int(number):
            min_ans = number
        return

    if sign_list[picked] == '>':

        for n in range(10):
            if numbers[picked] > n and visited[n] == 0:
                numbers.append(n)
                visited[n] = 1
                dfs(picked+1, numbers)
                numbers.pop()
                visited[n] = 0
    elif sign_list[picked] == '<':

        for n in range(10):
            if numbers[picked] < n and visited[n] == 0:
                numbers.append(n)
                visited[n] = 1
                dfs(picked+1, numbers)
                numbers.pop()
                visited[n] = 0


N = int(input())
sign_list = list(map(str, input().split()))
visited = [0] * 10
max_ans = 0
min_ans = 9999999999
numbers = []
for n in range(10):
    visited[n] = 1
    numbers.append(n)
    dfs(0, numbers)
    visited[n] = 0
    numbers.pop()
print(max_ans)
print(min_ans)