[Python] set

Set

 

set(집합 자료형)의 특징은 크게 2개가 있다.

 

1. 중복을 허용하지 않는다.

2. 순서가 없다.

 

중복을 허용하지 않아서 중복을 제거하는 용도로 사용할 수 있다. 또 순서가 없기 때문에 인덱싱과 슬라이싱을 지원하지 않는다.

 

중복과 순서에 대한 특성을 사용하지 않을 때는 list보다는 set 자료형을 사용하는 것이 시간 절약에 좋다. 리스트는 인덱스 0부터 n까지 일일이 검사를 해야하므로 시간복잡도가 O(n) 이고, set은 O(1)이라고 한다.

 

=> set 자료형을 사용하면 탐색시간을 줄여준다.

 

백준 1920번 문제가 대표적이다.

a = int(input())
b = set(map(int, input().split()))
c = int(input())
d = list(map(int, input().split()))

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

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

1920번: 수 찾기