정수로만 이루어진 배열 nums와 숫자 k가 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 정확히 k개의 요소를 제거한 후 남아 있는 고유(unique) 요소의 최소 개수를 찾는 것입니다.
문제 이해하기
예를 들어 입력이 다음과 같다면,
- nums = [5, 4, 2, 2, 4, 4, 3]
- k = 3
출력은 2가 됩니다. 그 이유는 5와 3을 제거하고, 2 또는 4 중 하나를 추가로 제거하면 배열에는 2와 4 두 종류의 값만 남기 때문입니다.
접근 방법: 그리디(Greedy) 전략
고유 요소의 개수를 최대한 줄이려면 등장 빈도가 낮은 숫자부터 우선적으로 제거하는 것이 유리합니다. 빈도가 낮은 숫자 하나를 제거하면 해당 숫자가 완전히 사라져 고유 요소 개수가 1씩 줄어들기 때문입니다.
이를 위해 다음 단계를 따릅니다.
- 각 숫자의 등장 횟수를 저장할 딕셔너리(빈도 맵)를 생성합니다.
- nums의 각 숫자를 순회하며 빈도를 기록합니다. 처음 나온 숫자라면 1로 설정하고, 이미 존재한다면 값을 1 증가시킵니다.
- count 변수를 딕셔너리의 크기(고유 숫자의 개수)로 초기화합니다.
- 딕셔너리의 모든 빈도 값을 오름차순으로 정렬하여 순회하면서 k에서 해당 빈도를 차감합니다.
- 차감 후 k가 음수가 되면 더 이상 제거할 수 없으므로 현재 count를 반환합니다.
- 그렇지 않으면 해당 숫자를 완전히 제거한 것이므로 count를 1 감소시킵니다.
- 모든 빈도를 처리한 후 최종 count를 반환합니다.
구현 예제
def solve(nums, k):
dictionary = {}
for num in nums:
if num not in dictionary:
dictionary[num] = 1
else:
dictionary[num] += 1
count = len(dictionary)
for frequency in sorted(dictionary.values()):
k -= frequency
if k < 0:
return count
else:
count -= 1
return count
nums = [5, 4, 2, 2, 4, 4, 3]
k = 3
print(solve(nums, k))입력
[5, 4, 2, 2, 4, 4, 3], 3
출력
2
동작 과정 살펴보기
위 예제에서 각 숫자의 빈도는 다음과 같습니다.
- 5 → 1회
- 3 → 1회
- 2 → 2회
- 4 → 3회
정렬된 빈도 순서는 [1, 1, 2, 3]입니다. k = 3이므로:
- 첫 번째 빈도 1을 차감 → k = 2, count = 3 (숫자 5 제거)
- 두 번째 빈도 1을 차감 → k = 1, count = 2 (숫자 3 제거)
- 세 번째 빈도 2를 차감 → k = -1, 음수이므로 즉시 count인 2를 반환
복잡도 분석
- 시간 복잡도: O(n log n) — 빈도를 계산하는 데 O(n), 빈도 값을 정렬하는 데 O(u log u)(u는 고유 숫자의 개수)가 소요됩니다.
- 공간 복잡도: O(n) — 각 숫자의 빈도를 저장하는 딕셔너리가 필요합니다.
이처럼 빈도 기반 그리디 접근법을 활용하면 k개의 요소를 제거한 후 남는 고유 정수의 최소 개수를 효율적으로 구할 수 있습니다.