•
문제 설명 : 제공된 숫자로 구성된 배열 중, k를 만들 수 있는 쌍이 몇개인지 반환
•
풀이 방법
◦
Two Pointer 문제라고 해서, 억지로 2개의 커서로 문제를 풀고 있었다.
◦
하지만 이 문제는 2개의 값을 합산하는 Two Sum 문제이기 때문에, 이 경우 바로 Hash Table을 떠올려야한다.
▪
이것을 미처 생각 못해서, 거의 Easy급 문제인 이 문제에 너무 많은 시간을 써서 아쉬웠다.
◦
Counter 를 사용하여, 요소의 갯수를 확인 후, 이를 사용하여 문제를 해결했다.
•
시간복잡도 :
•
성공 코드
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
cursor = 0
result = 0
num_count_info = Counter(nums)
for i, num in enumerate(nums):
if num >= k:
continue
if num_count_info.get(num, 0) > 0 and num_count_info.get(k - num, 0) > 0:
if num * 2 == k:
if num_count_info[num] >= 2:
num_count_info[num] -= 2
result += 1
else:
num_count_info[num] -= 1
num_count_info[k - num] -= 1
result += 1
return result
Python
복사
•
더 빠른 성공 코드
Solved는 했지만, 상대적으로 느린 시간으로 Solved되었다.
다른 사람들의 코드를 보니, Counter 를 사용하여 초반에 모든 요소의 갯수를 구하지 않고 현재 탐색 위치 앞 부분의 요소만 Hash Table을 사용하여 구하였다.
이 방법을 사용하면, O(2 * N) → O(N)으로 시간을 더 줄일 수 있다.
from collections import defaultdict
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
result = 0
num_count_info = defaultdict(int)
for i, num in enumerate(nums):
if num >= k:
continue
if num_count_info[k - num] > 0:
num_count_info[k - num] -= 1
result += 1
else:
num_count_info[num] += 1
return result
Python
복사