문제 이해하기
정수 배열 nums와 값 k가 주어진다고 가정해 보겠습니다. 한 번의 연산에서는 배열에서 두 원소를 선택했을 때 그 합이 정확히 k가 되면 해당 원소 두 개를 배열에서 제거할 수 있습니다. 이때 수행할 수 있는 최대 연산 횟수를 구하는 것이 이 문제의 목표입니다.
예를 들어, nums = [8, 3, 6, 1, 5], k = 9인 경우를 살펴보겠습니다. 먼저 합이 9가 되는 [3, 6]을 제거하고, 이어서 역시 합이 9가 되는 [8, 1]을 제거할 수 있으므로 정답은 2가 됩니다.
접근 방법
이 문제는 해시 맵(Python의 Counter)을 활용해 각 숫자의 등장 횟수를 미리 세어 둔 뒤, 현재 숫자와 짝이 되는 k - num의 개수를 확인하는 방식으로 효율적으로 해결할 수 있습니다.
counter:=nums에 포함된 각 숫자의 빈도수를 저장하는 맵(Counter)res:= 0으로 초기화- counter의 각 숫자
num에 대해 반복:counter[k - num]이 0이 아니라면:num이k - num과 다른 경우:res에counter[num]과counter[k-num]중 작은 값을 더한 뒤, 두 카운트를 모두 0으로 초기화하여 중복 계산을 방지합니다.num이k - num과 같은 경우(즉,num × 2 = k): 같은 숫자끼리 짝을 이루므로res에counter[num]을 2로 나눈 몫을 더합니다.
- 최종 결과
res를 반환합니다.
구현 예제
다음 Python 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import Counter def solve(nums, k): counter = Counter(nums) res = 0 for num in counter: if counter.get(k-num, 0): if num != k - num: res += min(counter[num], counter[k-num]) counter[k-num] = 0 counter[num] = 0 else: res += int(counter[num] / 2) return res nums = [8,3,6,1,5] k = 9 print(solve(nums, k))
입력
[8,3,6,1,5], 9
출력
2
복잡도 분석
시간 복잡도: O(n) — 배열을 한 번 순회하여 빈도수를 계산하고, 고유한 숫자의 개수만큼만 반복하기 때문입니다.
공간 복잡도: O(n) — 각 숫자의 빈도수를 저장하기 위한 해시 맵이 추가로 필요합니다.