[Python] 2529번 부등호

문제

https://www.acmicpc.net/problem/2529

풀이과정

• 입력
  부등호 개수, 부등호 나열된 것

• 출력
  관계를 만족하는(부등호가 성립하는) 최대, 최소 정수 나열 리스트 출력

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

dfs함수에 count가 n+1개가 되면 정답배열에 숫자 문자열을 넣고 종료

→ 0~9 숫자 반복, 사용한 숫자 제외, 결과값에 저장, 방문한 것 고려하기, 재귀하고 방문처리 지우기

정답배열을 오름차순 정렬하여 최댓값[-1], 최소값[0] 출력

• 방문 처리를 지우는 이유
  백트래킹 때문에 → 0으로 반복문을 돌렸으면 해당 숫자는 사용하면 안되기 때문에 1로 한 뒤에 재귀를 수행하고 다음으로 1로 반복문을 돌려야하는데 이때 0을 다시 사용해야 하기 때문에 0으로 설정한 뒤 다음 for문을 수행하는 것이다.

import sys 
input = sys.stdin.readline

n = int(input())
signs = list(input().split())
visited = [0] * 10
result = []

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

def dfs(cnt, num):
    if cnt == n + 1: # 모든 숫자를 사용 완료
        result.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]): # 첫번째 숫자일때(그냥 선택가능) or 부등호 조건 만족할때
            visited[i] = 1 # 현재 선택된 숫자가 사용되지 않도록 방지 
            dfs(cnt+1, num+str(i)) # 현재까지 생성한 문자열 num에 추가해서 다음거 호출 
            visited[i] = 0 # 다음 반복에서 사용할 수 있게 

dfs(0, '')
result.sort()
print(result[-1])
print(result[0])