[BOJ/백준] 2529번 부등호 (Python 파이썬)

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	17902	9743	6582	52.681%

문제

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

 

예제 입력 1 

2
< >

 

예제 출력 1 

897
021

 

예제 입력 2 

9
> < < < > > > < <

 

예제 출력 2 

9567843012
1023765489

 

---

풀이

이 문제도 먼저 제약 조건을 설정해봅시다.
간단히 요약하면 인접한 숫자끼리 주어진 부등호가 성립하는 것이 조건입니다.
그리고 해당 조건을 만족하는 수의 최소값과 최대값을 출력해야 합니다.

제약 조건

먼저 조건을 구체화 시켜보겠습니다.

문제에서 숫자는 입력으로 주어지는 것이 아니라 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택하여 직접 수열을 구성하는 것입니다. 문제 조건 상 0부터 삽입하여 수열을 순차적으로 늘려가겠습니다.
우선, 숫자를 담는 리스트, s와 부등호를 담는 리스트, sign으로 분리하였습니다.

예를 들어서 1 <  2 를 검사한다고 가정해봅시다. 그렇다면 s = "1" , sign= [ '<'] 와 같이 리스트가 채워지고 2를 검사해야합니다.
주어진 식이 참인지 판단하는 함수 check(왼쪽 숫자, 오른쪽 숫자, 부등호)를 만들었다면, 각 인자에는 어떤 값이 들어가야 할까요? 
현재 상황은, 반복문을 통해 0부터 9까지 i를 설정했을 때, i가 2인 차례입니다.
이때 check에 들어갈 인자를 하나씩 살펴보겠습니다.

1. 왼쪽 숫자 : 현재 담겨진 숫자 중에서 가장 마지막 숫자를 꺼내야 하므로, s[-1]입니다.
2. 오른쪽 숫자 : 현재 s에 삽입을 시도하는 숫자, 즉 i입니다. 이때 check의 동작을 위해 string으로 타입을 변환하여 str(i)으로 넘겨줍니다.
3. 부등호 : 현재의 탐색에서 검사하고 있는 부등호의 위치가 필요합니다. 헷갈리면 안되는게 i는 0부터 9까지 숫자 중 하나로 현재 삽입을 시도하고 있는 다음 숫자입니다. 따라서 탐색의 depth를 설정해서 정확히 해당 깊이의 탐색에서의 부등호를 가져와야 합니다.
   예를 들어서 sign = [ '>', '<', '>']이라면, 첫번째 숫자와 두번째 숫자를 검증하기 위해서는 sign[0]이 필요하고,
   두번째 숫자와 세번째 숫자를 검증하기 위해서는 sign[1]이 필요합니다.

check(s[-1], str(i), sign[depth-1])

이를 토대로 함수를 만들어 보면,

def check(i, j, k):
    if k == "<":
        return i < j
    else:
        return i > j

이를 통해서 제약 조건에 따른 가지치기를 진행할 수 있습니다.

풀이 code

from sys import stdin
input = stdin.readline

K = int(input())
sign = list(input().split())

visited = [0]*10
max_ans = ""
min_ans = ""


def check(i, j, k):
    if k == "<":
        return i < j
    else:
        return i > j


def solve(depth, s):
    global max_ans, min_ans

    if(depth == K+1):
        # 맨 처음 생성, 최소값
        if len(min_ans) == 0:
            min_ans = s
        # 계속 대입, 마지막에는 최대값
        else:
            max_ans = s
        return

    for i in range(10):
        if not visited[i]:
            if(depth == 0 or check(s[-1], str(i), sign[depth-1])):
                visited[i] = True
                solve(depth+1, s+str(i))
                visited[i] = False


solve(0, "")
print(max_ans)
print(min_ans)