[Baekjoon 2529 / Python / 실버1] 부등호

문제

테스트 케이스

 

import sys

input = sys.stdin.readline

N = int(input()) # 부등호 개수

boo = list(input().split()) # 부등호 리스트

result = []

visited = [False] * 10 # depth는 숫자 개수만큼

def compare(a, b, op):

    if op == '>':

        if a < b: return False

    elif op == '<':

        if a > b: return False

    return True

# 깊이, 현재숫자(문자열)

def backTracking(depth, num):

    # 숫자가 완성되었다면 결과 리스트에 추가

    if depth == N + 1:

        result.append(num)

        return

   

    for i in range(10):

        if not visited[i]:

            if depth == 0 or compare(num[-1], str(i), boo[depth-1]):

                visited[i] = True

                backTracking(depth + 1, num + str(i))

                visited[i] = False

backTracking(0, '')

print(max(result))

print(min(result))

 

백트래킹 문제이다. 처음엔 부등호 조건을 검사할 때 int로 변환시켜 비교하기 위해서, 맨앞 숫자가 0일경우 0을 빼는 로직을 추가하느라 복잡해졌었다. 하지만 같은 자리수의 숫자끼리는 문자열 상태로 비교해도 int형을 비교하는 것과 완벽하게 같은 효과를 갖는다는 것을 깨닫고 수정했다. min, max 함수에도 적용되는 듯 하다.

 

또한 부등호 조건을 검사하는 함수를 따로 빼두니 코드가 훨씬 간결해졌다. 자잘한 조건들을 제외하면 굉장히 무난한 백트래킹 문제였던 것 같다.