백준 2529 | 부등호, Permutation

 

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

예제 입력 1 복사

2
< >

예제 출력 1 복사

897
021

예제 입력 2 복사

9
> < < < > > > < <

예제 출력 2 복사

9567843012
1023765489

 

 

 

처음 문제를 접했을 때 단순히 푸는 것 그 자체에

너무 집중한 나머지 어떻게 풀어나가야할지 잘 감이 오지 않았다.

 

해설의 도움을 힌트삼아

차근차근 풀어나가보자.

 

먼저 수열의 방식을 이용해 풀었다.

모든 수열의 경우의 수를 다 구한 후,

그 중에서 부등호 기호를 만족하는

최댓값, 최소값을 구하는 방식으로 풀었다 (해설이).

 

 

그렇게 했을 때 시간 복잡도가 너무 떨어지지 않을까

염려스러웠는데, 그래서 다른 풀이도 있나

찾아보니 BackTracking 방식이 있더라.

 

 

먼저 Permutation 함수를 이용해 모든 수열 경우의 수를 구한다음.

check 라는 함수를 만들어서 조건을 걸어주고 부등호에 맞는

수열을 찾는 방식이다.

 

 

각 두 개의 for loop를 걸어서

최댓값, 최솟값을 각각 구해주면 끝.

 

 

 

 

import sys
from itertools import permutations

K = int(sys.stdin.readline())
arr = list(sys.stdin.readline().split())
numbers = [0,1,2,3,4,5,6,7,8,9]

nPr = list(permutations(numbers,K+1))


def check_ok(numbers):
    flag = True
    for i in range(0,K):
        if arr[i] == '<':
            if not numbers[i] < numbers[i+1]:
                flag = False
                break
        if arr[i] == '>':
            if not numbers[i] > numbers[i+1]:
                flag = False
                break
    return flag

for x in reversed(nPr):
    if check_ok(x):
        for i in x:
            print(i,end='')
        break
print()

for x in nPr:
    if check_ok(x):
        for i in x:
            print(i, end='')
        break

 

 

 

 

아래는 Backtracking 을 이용해 푼 코드.

space complexity 면에서 훨씬 우월하다.

 

시간 복잡도면에서도 위의 코드보다 훨씬 빠름.

 

 

from itertools import permutations

def check(x, y, op):
    if op == '<':
        return x < y
    return x > y

def solve(n, operators):
    digits = list(range(10))
    valid_numbers = []
    
    for perm in permutations(digits, n + 1):
        valid = True
        for i in range(n):
            if not check(perm[i], perm[i + 1], operators[i]):
                valid = False
                break
        if valid:
            valid_numbers.append("".join(map(str, perm)))
    
    valid_numbers.sort()
    print(valid_numbers[-1]) 
    print(valid_numbers[0])   

if __name__ == "__main__":
    n = int(input().strip())
    operators = input().split()
    solve(n, operators)

 

 

 

사실 개인적으로 이 문제는 어려워서,

며칠 더 고민해봐야 완벽히 이해될듯하다.