[BOJ/Python] 2529 부등호

📌 문제

[백준] 2529 부등호

📌 풀이

1. 완전 탐색 가능 여부 판단

• 선택해야 하는 숫자의 개수는 부등호의 개수 +1 개이고, 부등호의 개수인 K는 최대 9이므로 최대 10개의 숫자(0~9)를 선택해야 함
• N개의 숫자를 순서를 고려해서 나열하는 것 = 순열(Permutation)
• 가능한 최대의 경우의 수는 K=9일 때 10! = 3628800 ⇒ 시간 내에 충분히 완전 탐색 가능!

2. 순열 구현

intertools 의 permutations 라이브러리 사용하기!

3. 순열의 부등호 만족여부 확인

• permutations 라이브러리를 통해 가능한 permutation list를 만든 후, 이 순열이 부등호를 만족하는지 확인해야 함.
• 동시에 부등호를 만족하는 최대/최소 정수를 출력해야 하므로 순열 리스트를 각각 내림차순/오름차순으로 정렬하여 최댓값과 최솟값을 구해야 함.

📌 코드 설계

1. 문제의 입력값 받기
2. K+1개의 숫자를 선택하는 모든 순열 구하기
3. 순열의 부등호 만족 여부 확인 함수 구현하기
4. 최댓값 찾기: 내림차순으로 정렬하여 탐색하기
5. 최솟값 찾기: 오름차순으로 정렬하여 탐색하기

📌 정답 코드

import sys
from itertools import permutations

# 1. 문제의 입력값 받기
K = int(sys.stdin.readline())
arr = list(sys.stdin.readline().split())
numbers = [0,1,2,3,4,5,6,7,8,9]

# 2. K+1개의 숫자를 선택하는 모든 순열 구하기
per_list = list(permutations(numbers,K+1))

# 3. 순열의 부등호 만족 여부 확인 함수 구현하기
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

# 4. 최댓값 찾기: 내림차순으로 정렬하여 탐색하기
for x in reversed(per_list):
    if check_ok(x):
        for i in x:
            print(i, end='')
        break
print()

# 5. 최솟값 찾기: 오름차순으로 정렬하여 탐색하기
for x in per_list:
    if check_ok(x):
        for i in x:
            print(i, end='')
        break