[Baekjoon] 2529 부등호 python

🏷 문제

💡 코드

from sys import stdin

# 숫자를 추가할 때마다 비교해주는 함수
def compare_num(n1, n2, op):
    if op == '<':
        if n1 < n2:
            return True
        else:
            return False
    else:
        if n1 > n2:
            return True
        else:
            return False

def solve(idx, s):
    global max_res, min_res
    # 종료 조건 : 숫자 개수가 K+1개 일 때(부등호 개수가 K이므로)
    if idx == K + 1:
        # 0부터 탐색하기 때문에 뒤에 나오는 조합(?)이 무조건 더 크게 되어있음
        # min_res에 값이 없다면 s를 최소값으로
        if(len(min_res) == 0):
            min_res = s
        # min_res에 값이 있다면 s를 최대값으로 설정
        else:
            max_res = s
        return

    for i in range(10):
        # 해당 숫자를 아직 사용하지 않았다면
        if check[i] == False:
            # s[-1] : 현재 문자열에 있는 문자 중 가장 뒤의 문자
            # str(i) : 비교해야할 문자
            if idx == 0 or compare_num(s[-1], str(i), operators[idx - 1]) == True:
                check[i] = True
                solve(idx + 1, s + str(i))
                check[i] = False

K = int(stdin.readline())
operators = list(stdin.readline().split())

# 0~9까지의 수를 사용했는지 체크
check = [False] * 10
max_res = ""
min_res = ""

solve(0, "")

print(max_res)
print(min_res)

🔑

백트래킹을 이용해 풀어야 하는 문제 !
나에겐... 너무 어려웠다....😂
이런 비슷한 유형의 문제를 찾아 풀면서 감을 더 익혀야 겠다