[백준] 2529 - 부등호 / Python / 실버 1

🚩문제 주소

📄풀이

백트래킹

check 함수

숫자와 부등호를 인자로 받아서 성립하지않으면 False, 성립하면 True 반환

dfs 함수

카운트가 K+1과 같아지면 정답배열에 숫자문자열을 넣고 종료

0~9 숫자 반복
사용한 숫자라면 패스
카운트가 0 이거나 check함수가 True라면 숫자를 방문처리하고 재귀한 후, 방문처리한 것을 지움

숫자문자열들이 담긴 정답배열을 오름차순으로 정렬한 다음, 마지막과 처음을 나눠서 출력합니다.

👨‍💻코드

def check(a, b, op):
  if op == '<':
    if a > b: return False
  if op == '>':
    if a < b: return False
  return True

def dfs(cnt, num):
  if cnt == k+1:
    answer.append(num)
    return
  
  for i in range(10):
    if visited[i]: continue

    if cnt == 0 or check(num[cnt-1], str(i), signs[cnt-1]):
      visited[i] = 1
      dfs(cnt+1, num+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])