백준 2529번(부등호) 파이썬

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

2529번: 부등호

이 문제는 처음에 쉽게 생각했다.

지금까지 풀었던 문제들과 크게 다를게 없구나 하고 막힘없이 풀어 갔다. 그리고 예제들을 돌렸을때 잘 나오길래 오 됐다!!

하고 제출을 했는데... "시간초과" 가 떠버렸다... 그래서 pypy3로 돌려봤는데 여기선 정답이 떴다.

하지만 python3로 정답이 떠야 하기 때문에 다시 풀어보려다 실패하고 결국 다른 사람의 풀이를 참고하게 되었다.

아래는 풀이 코드이다.

import sys
input = sys.stdin.readline

k = int(input())
arr = list(input().split())
visited = [False]*10

ans = []
"""tmp = []

def dfs():
    if len(ans) == k+1:
        check = [False]*k
        for i in range(k):
            if arr[i] == '>':
                if ans[i]>ans[i+1]:
                    check[i] = True
                    continue
                else:
                    break
            else:
                if ans[i]<ans[i+1]:
                    check[i] = True
                    continue
                else:
                     break
        if False not in check:
            tmp.append(''.join(map(str,ans)))
        return
    for i in range(10):
        if visited[i]:
            continue
        visited[i]=True
        ans.append(i)
        dfs()
        ans.pop()
        visited[i]=False

dfs()
print(max(tmp))
print(min(tmp))"""

def check_up(i, j, k): # True, False를 판단해줄 함수
    if k == '<':
        return i < j
    else:
        return i > j

def dfs(iter, temp):
    if iter == k + 1: # 문자열의 길이가 k+1의 자리가 될 때
        ans.append(temp)
        return

    for i in range(10):
        if not visited[i]:
            # 문자열의 길이가 0이거나 부등호의 수식이 True일때
            if iter == 0 or check_up(temp[-1], str(i), arr[iter - 1]): 
                visited[i] = 1
                dfs(iter + 1, temp + str(i)) # 다음 수식들을 또 검사해준다
                visited[i] = 0
dfs(0, "")

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

주석 처리가 된 부분은 시간초과가 났던 코드이다.

시간 초과가 난 이유는 삽입과 삭제 부분 때문이 아닐까 추측된다..

혹시 제 코드의 시간초과의 이유를 아시는 분은 댓글로 알려주시면 감사하겠습니다!