글 읽기 - 시간초과를 받는 기준이 궁금합니다 (답안 있음)

qusworud 10일 전 0

파이썬 3로 답안 코드를 제출하고 시간초과를 받아 마지막 동앗줄 잡는 격으로 PyPy3로 그대로 다시 제출했는데 다행히도 통과를 받아 시간복잡도를 줄이기 위해 로직 전체를 갈아엎는 대참사는 안벌어졌습니다

여기까진 좋은데 반례 찾는 사이트인

여기서 반례를 검토해보면 가장 극단적으로 긴 데이터 입출력의 테스트 케이스에선

PyPy3로도 결과까지 8초가 넘게 걸려 얄짤없이 TLE가 선언되더라고요

백준 채점 데이터엔 이런 극단적인 데이터가 없는걸까요?

아니면 그냥 사이트마다 차이가 있는걸까요?

import sys
input = sys.stdin.readline
print = sys.stdout.write

bump = 1
out = ""
stack = []
command = []

n = int(input())
for i in range(n):
    x = int(input())
    # 스택에 그 원소가 없다면
    if stack.count(x)==0:
        # 그 원소까지 쌓을수 있을때
        if bump <= x:
            # 그 원소를 넣을때까지 쌓고
            while stack.count(x) == 0:
                stack.append(bump)
                bump += 1
                command.append("+")
            # 그 원소 빼기
            stack.pop()
            command.append("-")
        # 이미 지나쳤다면
        else:
            print("NO")
            exit()
    else:
        # 스택에 그 원소를 뺄때까지 계속 빼기
        while out != x:
            out = stack.pop()
            command.append("-")

print("\n".join(command))