문제
K개의 부등호가 주어질 때, 0~9 숫자를 중복 없이 배치하여 부등호를 만족하는 최대/최소 수를 구하라.
입력
부등호 개수 K와 K개의 부등호가 주어진다.
출력
조건을 만족하는 최댓값과 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 < > | 897 021 |
풀이
백트래킹으로 모든 가능한 배치를 탐색한다.
- 0~9 숫자를 하나씩 선택하며 부등호 조건을 확인한다
- 조건을 만족하면 다음 자리로 진행, 불만족하면 가지치기한다
- K+1개 숫자를 모두 배치한 결과를 저장한다
- 결과를 정렬하여 최대/최소를 출력한다
핵심 아이디어: K는 최대 9이므로 백트래킹의 탐색 공간이 10!로 제한되어 충분히 빠르다.
코드
K = int(input())
signs = list(map(str,input().split(' ')))
nums = [-1] * 10
result = []
def solution(depth, prev, value):
if depth == K+1:
result.append(value)
else:
for i in range(10):
if nums[i] == -1:
nums[i] = 1
if signs[depth-1] == '<' and ( prev < i ):
solution(depth+1, i, value+str(i))
elif signs[depth-1] == '>' and ( prev > i ):
solution(depth+1, i, value+str(i))
nums[i] = -1
for i in range(10):
nums[i] = 1
solution(1, i, str(i))
nums[i] = -1
result.sort()
print(result[-1])
print(result[0])복잡도
- 시간: O(N!)
- 공간: O(N)