파이썬 집합 메소드와 시간복잡도

문제 설명

파이썬 집합(set) 자료형에서 자주 사용되는 여러 메소드명 중 하나가 입력값으로 주어졌을 때, 해당 메소드의 시간복잡도를 빅오(Big-O) 표기법으로 반환하는 solution 함수를 작성하시오.

입력값으로 메소드명은 "add", "remove", "discard", "pop", "clear", "union", "intersection", "difference", "issubset" 중 하나이며, 해당 메소드의 시간복잡도를 "O(1)", "O(logN)", "O(N)", "O(NlogN)" 중에서만 반환하세요.

각 표기에서 N은 집합의 원소 수를 의미합니다.

⸻

개념 설명

파이썬 집합의 각 메소드별 시간복잡도는 다음과 같습니다:

• add: O(1) — 집합에 새로운 요소 추가(상수 시간)

• remove: O(1) — 특정 요소 제거(상수 시간)

• discard: O(1) — 특정 요소 제거(상수 시간, 요소가 없어도 오류 없음)

• pop: O(1) — 임의 요소 제거 및 반환(상수 시간)

• clear: O(1) — 모든 요소 삭제(상수 시간)

• union: O(N) — 두 집합의 합집합 반환(전체 순회 필요)

• intersection: O(N) — 두 집합의 교집합 반환(전체 순회 필요)

• difference: O(N) — 두 집합의 차집합 반환(전체 순회 필요)

• issubset: O(N) — 부분집합 여부 확인(전체 순회 필요)

입력으로 제공된 메소드명은 항상 소문자로만 이루어져 있습니다.

⸻

제한 사항

• method는 반드시 아래 메소드 목록 중 하나로 주어집니다.

• 입력되는 메소드 목록: add, remove, discard, pop, clear, union, intersection, difference, issubset

• 입력 메소드명은 소문자로만 이루어져 있습니다.

⸻

예시 테스트케이스 설명

1번 테스트케이스 설명

• “add”는 집합에 요소를 삽입할 때 해시 구조를 사용하여 평균적으로 매우 빠른 O(1)의 시간복잡도를 보입니다.

2번 테스트케이스 설명

• “intersection”은 두 집합의 교집합을 구하는 과정에서 한 집합 내의 모든 요소를 다른 집합에서 확인해야 하므로 O(N)가 소요됩니다.

3번 테스트케이스 설명

• “issubset”은 현재 집합의 모든 요소가 다른 집합에도 있는지 확인하는 과정이 필요하므로 O(N)이 걸립니다.