숫자 리스트 items와 값 n이 주어졌다고 가정해 봅시다. 어떤 영업 사원이 무작위 ID를 가진 아이템들을 가방에 담고 있으며, 가방에서 최대 n개의 아이템을 제거(판매)할 수 있습니다. 우리의 목표는 n개를 제거한 후 가방에 남아 있는 서로 다른 ID의 최소 개수를 구하는 것입니다.
예를 들어 입력이 items = [2, 2, 6, 6], n = 2라고 해봅시다. 이 경우 출력은 1이 됩니다. ID가 2인 아이템 두 개 또는 ID가 6인 아이템 두 개를 판매하면, 남은 아이템들은 하나의 ID만 가지게 되기 때문입니다.
문제 해결 접근 방식
이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 핵심 아이디어는 빈도수가 가장 낮은 ID부터 우선적으로 제거하면, 제거 횟수 n 안에서 최대한 많은 종류의 ID를 없앨 수 있다는 점입니다. 단계별로 살펴보면 다음과 같습니다.
- c := items에 있는 각 요소의 빈도수를 계산
- ans := c의 크기 (서로 다른 ID의 개수)
- freq := c의 모든 빈도수를 오름차순으로 정렬한 리스트
- i := 0
- i가 freq의 길이보다 작은 동안 반복:
- 만약 freq[i] <= n이라면:
- n := n - freq[i] (해당 ID 전체를 제거)
- ans := ans - 1 (ID 종류 하나 감소)
- 그렇지 않으면:
- ans 반환 (더 이상 완전히 제거할 수 있는 ID가 없음)
- i := i + 1
- 만약 freq[i] <= n이라면:
- 0 반환
파이썬 구현 예제
다음 코드를 통해 더 잘 이해할 수 있습니다:
from collections import Counter
class Solution:
def solve(self, items, n):
c = Counter(items)
ans = len(c)
freq = sorted(c.values())
i = 0
while i < len(freq):
if freq[i] <= n:
n -= freq[i]
ans -= 1
else:
return ans
i += 1
return 0
ob = Solution()
items = [2, 2, 6, 6]
n = 2
print(ob.solve(items, n))
입력
[2, 2, 6, 6], 2
출력
1
동작 원리 및 복잡도 분석
위 예제에서 Counter(items)는 {2: 2, 6: 2}라는 빈도수 딕셔너리를 생성합니다. 초기 ans는 2(ID 종류 수)이고, 정렬된 빈도수 리스트는 [2, 2]입니다. 첫 번째 빈도수 2는 n(=2)보다 작거나 같으므로 해당 ID를 모두 제거하고 ans는 1이 됩니다. 다음 빈도수 2는 남은 n(=0)보다 크므로 즉시 1을 반환합니다.
이 알고리즘의 시간 복잡도는 빈도수 계산에 O(N), 정렬에 O(K log K)(K는 서로 다른 ID의 개수)가 소요되므로 전체적으로 O(N + K log K)입니다. 공간 복잡도는 빈도수 저장을 위해 O(K)입니다.