글 읽기 - 7785번 시간초과 이슈입니다.

jayb100 4년 전 0

안녕하세요, 여러 방법을 시도해도 계속 시간 초과가 떠서 질문 드립니다. ㅠ

제 코드는 아래와 같은데 여러 시도를 거쳤는데도 계속 시간 오류가 나네요..

for문이라 무한 반복은 아닌것 같은데 이유를 모르겠습니다.

vs code에서 실행하면 예제는 제대로 출력되는데 시간 초과가 나는 이유를 정말 모르겠습니다. ㅠ

시간 초과 뿐만 아니라 코드에 대한 코멘트 아무거라도 추가해주시면 정말 감사하겠습니다!

감사합니다!

from sys import stdin
n = int(stdin.readline()) # 회사 출입 기록
worklist = [] # 회사에서 일하고 있는 사람
wa = worklist.append
wr = worklist.remove
for _ in range(n): 
    name, work = stdin.readline().strip().split() # 명령문 입력 받기
    if work == "enter": 
        wa(name)
    else :
        try:
            wr(name)
        except:
            continue    
for lst in sorted(worklist, reverse = True):
    print(lst)

shg9411 4년 전 1

리스트에서의 삭제 연산은 O(n)이 소요됩니다. n은 최대 10^6이고.. O(n^2)의 이 코드는 시간초과가 나겠죠..?

자료구조를 활용해보세요.

jayb100 4년 전 1

답변 정말 감사합니다! 아직 O()에 대한 개념이 없어서 문제를 풀 때 속도 계산하는게 어렵네요..

덕분에 dict로 해서 풀었습니다!

왠만하면 그냥 append remove를 하면 안될 것(?) 같네요

힌트 주셔서 정말 감사합니다!

from sys import stdin
n = int(stdin.readline()) # 회사 출입 기록
worklist = dict() # 회사에서 일하고 있는 사람
for _ in range(n):
    name, work = stdin.readline().strip().split()
    if work == "enter":
        worklist[name] = 1
    else :
        worklist[name] = 0    
working = sorted(worklist.items(), key= lambda x : x[0], reverse = True)
for nme, status in working:
    if status:
        print(nme)

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

문제

문제

출처

ICPC

7785번 시간초과 이슈입니다.

jayb100 4년 전 0

shg9411 4년 전 1

jayb100 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말