글 읽기 - 시간초과에 대해서 해결하고자 올립니다.

wmfrlek1107 1년 전 0

50퍼에서 시간초과가 걸립니다. 이유가 무엇일까요?

# 문제 접근

# 문자를 입력받을 때 마다 cnt 1씩 증가 이때 cnt는 인덱스접근을 위한 변수 이후 < 또는 > 만나면 cnt 증가 감소 진행 그 이후 insert로 삽입
import sys


testcase = int(sys.stdin.readline())

for i in range(testcase):
    answer = []
    cnt =0
    text = sys.stdin.readline()
    for i in text:
        if i == '<':
            if cnt > 0:
                cnt -= 1
        elif i == '>':
            if cnt < len(text) and cnt <= len(answer)-1:
                cnt +=1
        elif i == '-':
            if cnt != 0:
                del answer[cnt-1]
                cnt -=1
        else:
            answer.insert(cnt,i)
            cnt +=1
    for i in answer:
        print(i,end="")

adung7 1년 전 1

리스트의 insert와 del 은 O(N)의 작업이므로 삽입과 삭제가 빈번하게 일어나는 이 문제에서는 적합하지 않은 방식입니다.

리스트말고 이 문제에 적합한 다른 자료구조로 풀어보시길 바랍니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과에 대해서 해결하고자 올립니다.

wmfrlek1107 1년 전 0

adung7 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말