[백준] 부등호 - Python 파이썬

사용개념: 브루트포스, 완전탐색

 

1. 완전 탐색이 가능한지?

K는 최대 9이므로 최악의 경우 숫자를 뽑는 경우의 수가 10!(=3628800)개 생긴다. 이는 시간 제한 안에 충분히 탐색 가능하다.

2. 전체 코드

from itertools import permutations

k = int(input())
signs = list(input().split())

number = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
numbers = list(permutations(number, k+1))

def check(num):
    flag = True
    for i in range(k):
        sign = signs.pop(0)
        if sign == "<":
            if num[i] > num[i+1]:
                flag = False
        else:
            if num[i] < num[i+1]:
                flag = False
        signs.append(sign)
    return flag    
        
for num in reversed(numbers):
    if check(num):
        print(''.join(map(str, num)))
        break

for num in numbers:
    if check(num):
        print(''.join(map(str, num)))
        break

 

3. DFS

10개의 숫자를 부등호 조건에 맞게 조합하는게 0~9를 방문처리하면서 dfs를 돌릴 수 있을 것 같았다.

 

`방문처리` → `재귀` → `방문처리 해제`를 해줄 것.

 

def check(a, b, sign):
    if sign == "<":
        if not a < b: return False
    if sign == ">":
        if not a > b: return False
    return True

def dfs(cnt, number):
    if cnt == k+1:
        answer.append(number)
        return
        
    for i in range(10):
        if visited[i]: continue
        
        if cnt == 0 or check(number[cnt-1], str(i), signs[cnt-1]):
            visited[i] = 1
            dfs(cnt+1, number+str(i))
            visited[i] = 0            
            
k = int(input())
signs = list(input().split())
visited = [0] * 10
answer = []
dfs(0, '')
answer.sort()
print(answer[-1])
print(answer[0])