인프런 커뮤니티 질문&답변

이도열님의 프로필 이미지

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

백준 10815번 list와 set차이

해결된 질문

23.01.20 20:01 작성

·

440

·

수정됨

0

안녕하세요, 선생님

항상 강의 잘 듣고 있습니다.

 


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

 

제가 백준을 푸는데, 이 10815번 문제가 list로 찾으면 시간 초과가 뜨고, set으로 바꿔서 찾으면 시간 초과가 안뜨더라고요..

set이 순서가 없고, 중복이 안된다는것은 알고있습니다.

하지만 왜 set으로 바꿔서 속도가 빨라지는건지 궁금합니다.

 

list를 사용한 코드 - 시간 초과

N = int(input())
a = list(map(int, input().split()))
M = int(input())
b = list(map(int, input().split()))

for i in b:
    if i in a:
        print(1)
    else:
        print(0)

 

set을 사용한 코드

N = int(input())
a = set(map(int, input().split()))
M = int(input())
b = set(map(int, input().split()))

for i in b:
    if i in a:
        print(1)
    else:
        print(0)

 

감사합니다.

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

2023. 01. 23. 08:21

안녕하세요^^

리스트는 원소가 있는지 확인하는 in은 평균 시간복잡도가 O(n)이고,

셋은 in의 평균 시간복잡도가 O(1) 입니다. 셋은 해쉬를 쓰기 때문에 그렇습니다.