글 읽기 - 1764번 듣보잡 문제 시간초과 이유를 모르겠습니다

dbw1s 1년 전 0

어느부분에서 시간초과가 일어난것인지 궁급합니다

또한 어떻게 해결해야할까요?

O(N) 이라고 생각하고 있는데 맞는지 궁금합니다

부탁드립니다

import sys
a, b = int(sys.stdin.readline().split())



name1, name2 = [],[]

for i in range(int(a)):
    name = sys.stdin.readline()
    name1.append(name)

for i in range(int(b)):
    name = sys.stdin.readline()
    name2.append(name)


SameList = []
cmp = 0
for i in range(int(a)):
    for k in range(int(b)):
        if ( name1[i] == name2[k]):
            SameList.append(name1[i])
            cmp += 1


SameList.sort()
print(cmp)
for i in range(cmp):
    print(SameList[i], end = "")

jiwon405 1년 전 0

두 리스트를 비교하는 이중 for문 연산의 시간복잡도가 O(len(name1) * len(name2)) 이여서 시간 초과가 발생한거같아요!!

힌트를 살짝 드리자면 이 문제는 list가 아닌 다른 자료형을 사용하셔야 시간초과가 안날겁니다!!

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

문제

문제

출처

ICPC

1764번 듣보잡 문제 시간초과 이유를 모르겠습니다

dbw1s 1년 전 0

jiwon405 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말