24.08.28 알고리즘 - 파이썬 내장 함수

set()

중복되지 않은 요소들의 집합을 저장한다.

순서가 없고, 중복되는 요소를 자동으로 제거한다.

 

주요 메서드

add(element) : 집합에 요소 추가

remove(element) : 집합에서 요소 제거. 만약 요소가 집합에 없으면 'KeyError' 발생

discard(elment) : 집합에서 요소 제거. 요소가 없어도 오류 발생X

clear() : 집합의 모든 요소 제거

union(other_set) : 두 집합의 합집합 반환

intersection(other_set) : 두 집합의 교집합 반환

difference(other_set) : 두 집합의 차집합 반환

 

 

백준 1822_차집합

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
a = set(map(int,input().split()))
b = set(map(int,input().split()))

result = sorted(a.difference(b))

if result:
    print(len(result))
    print(*result)
else:
    print(0)

 

간단한 문제라 쉽게 풀 것 같았지만 계속해서 시간초과가 발생했다.

리스트 a에서 리스트 b에 있는 요소들을 제거하는 작업, 'in' 연산은 O(n) 의 시간복잡도가 발생해서 시간초과가 발생한 것이었다.

그래서 set으로 변환하여 차집합을 구하면서 O(1)의 시간복잡도로 줄일 수 있었다.