여러 사람의 이름이 저장된 리스트에서 동명이인의 이름 집합을 반환하는 문제이다.
집합; Set
리스트와 같이 정보를 여러 개 넣어서 보관하는 자료구조
같은 자료가 중복되어 저장되지 않고, 자료의 순서에 의미가 없다.
선언 및 사용
# 선언
s = set()
# 값 추가
s.add(VAL)
# 값 삭제
s.discard(VAL)
# 집합 비우기
s.clear()
# 집합의 길이
len(s)
# 값의 존재 유무 확인
val in s # 값이 집합에 존재하면 True
val not in s # 값이 집합에 없으면 True자료의 순서에 의미가 없으므로 집합 {val1, val2}와 집합 {val2, val1}은 동일하다.
+
두 개의 중첩 반복문 내에서 비교하는 알고리즘의 계산 복잡도는 n-1까지의 합과 같다.
$$ \sum_{k=1}^{n-1} k = \frac{(n-1)(n-1+1)} {2} =\frac{n(n-1)} {2} = O(n^2) $$