[백준/파이썬] 2529 부등호

#문제링크

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

2529번: 부등호

#나의풀이

import sys

answer = []
visited = [0] * 10
N = 0

def check(num1, num2, op):
    if op == '>':
        if int(num1) > int(num2):
            return True
    if op == '<':
        if int(num1) < int(num2):
            return True
    return False

def DFS(L, num):
    if L == N:
        answer.append(num)
        return
    for i in range(10):
        if (not visited[i]):
            if L == 0 or check(num[L-1], str(i), S[L-1]):
                visited[i] = 1
                DFS(L+1, num+str(i))
                visited[i] = 0


if __name__=="__main__":
    T = int(sys.stdin.readline())
    S = list(sys.stdin.readline().split())
    N = len(S) + 1

    DFS(0, '')

    print(answer[-1])
    print(answer[0])

#해설

시간복잡도 계산해보면 전체 순열을 만들어서 되는지 판별후 답을 출력해도 돌아갈꺼 같긴 했다.

좀 더 시간을 개선하기 위해 백트래킹을 썼고 check함수는 두 숫자와 op를 보고 맞는 판별식인지 확인했고

DFS함수는 L이 N의 길이만큼 완성이 되면 결과배열에 넣어주고 반복문을 돌면서 조건에 맞다면 num을 완성시켜주었다.

조건문으로는 0~9까지 1번만 쓸수 있기 때문에 방문 배열로 체크해서 방문을 안했으면 조건식이 돌아가게 했고

0번째 자리면 무조건 들어가야 하기때문에 or을 사용해주었다.