TIL
24.08.28 알고리즘 - 파이썬 내장 함수
habbn
2024. 8. 28. 21:44
728x90
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)의 시간복잡도로 줄일 수 있었다.
728x90