[LeetCode] 1. Two Sum
1. Two Sum
Array Hash Map
기술 인터뷰에서도 자주 다루는 유형이다.
처음에는 가볍게 풀었지만 Beats38.07%가 나와서 다른 방식으로 풀어 Beats100.00%를 만들 수 있었다.
Problem
문제는 정수가 담긴 1차원 리스트가 주어졌을 때,
리스트안의 두 수의 합이 target의 값과 동일할 때 해당 값들의 인덱스를 리스트형식으로 반환하라는 내용이다.
부가적으로 O(n2)의 시간복잡도보다 더 효율적으로 짜보라는 코멘트가 있다.
Approach
일반적으로 두 가지 방식이 있다.
1. 2중 반복문을 사용하여 브루트포스 형식으로 모든 경우의 수를 구하는 경우
2. hashmap을 사용하여 보수를 이용하여 구하는 경우
1번의 경우 O(n2)의 시간복잡도를 가지게 되어서 비효율적이며 2번의 방식으로하면 O(n)의 시간복잡도로 구할 수 있다.
2번의 형태로 문제를 푼 과정은 아래와 같다.
현재 주의깊게 생각해볼 부분은 배열의 모든 숫자 X에 대해서 X + Y = target인 다른 숫자 Y를 찾고 있다는 것이다.
즉, 숫자 X에 있을 때 우리는 (target - X)를 찾고 있으며, 이를 보수라고 한다.
이를 슈도코드로 나타내보자.
- 배열의 정수와 index를 매핑 할 해쉬맵 변수를 하나 선언한다.
- 배열의 길이만큼 반복하며 해당 값 X에 대해서 아래의 과정을 수행한다.
- (Target - X)가 해쉬맵에 존재하는지 확인한다.
- 존재하는 경우, 두 정수의 인덱스 값을 반환한다.
- 존재하지 않는 경우. 해쉬 맵에 X와 X의 인덱스 값을 저장한다.
Source Code
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 해쉬맵에 배열의 정보를 [number, index]로 매핑하기
ht = {}
# 배열의 반복
for i, num in enumerate(nums):
# (target - num)이 해쉬맵에 존재하는지 check
if target - num in ht:
# 찾았다면 두 인덱스를 반환
return [ht[target-num], i]
# 현재 값의 인덱스를 해쉬맵에 저장
ht[num] = i
# 값을 찾을 수 없다면 빈 리스트 반환
return []
Result
시간복잡도: O(n)
Beats: 100.00%
처음에 작성한 코드
투 포인터로 풀었다.
이중 반복문 쓰기 싫어서 나름 생각해봤는데 다소 아쉬웠던 접근법이다.
# 시간복잡도: O(n) (리스트 수정) + O(n log n) (정렬) + O(n) (투 포인터 탐색) => O(n log n)
class Solution(object):
def twoSum(self, nums: List[int], target: int) -> List[int]:
result = []
for i in range(len(nums)):
nums[i] = [i, nums[i]]
sorted_nums = sorted(nums, key = lambda x: x[1])
left_idx, right_idx = 0, len(nums) -1
while left_idx != right_idx:
sum_num = sorted_nums[left_idx][1] + sorted_nums[right_idx][1]
# 두 수의 합이 target과 동일한 경우
if sum_num == target:
result.append(sorted_nums[left_idx][0])
result.append(sorted_nums[right_idx][0])
return result
# 두수의 합이 target보다 작은 경우
elif sum_num < target:
left_idx += 1
# 두수의 합이 target보다 큰 경우
else: right_idx -= 1
return []
슈도코드는 아래와 같다.
- 한번 오름차순으로 배열을 정렬을 시킨 후 왼쪽과 오른쪽의 인덱스를 나타내주는 변수를 각각 선언한다.
- 반복문을 돌면서 해당 인덱스에 해당하는 값들을 더해준다.
- 두 수의 합이 target과 동일한 경우, 왼쪽과 오른쪽의 인덱스를 반환한다.
- target보다 작을 경우, 왼쪽 인덱스를 1증가시킨다. # 왼쪽 인덱스가 커질 수록 값이 커지기 때문
- target보다 클 경우, 오른쪽 인덱스를 1감소시킨다. # 오른쪽 인덱스가 작아질 수록 값이 작아지기 때문
이렇게 했을 때는 그닥 효율이 좋지는 않았다.
전체 시간복잡도는 이렇게 된다.
O(n) (리스트 수정) + O(n log n) (정렬) + O(n) (투 포인터 탐색) => O(n log n)
시간복잡도: O(nlogn)
Beats: 52.10%
// 기존에 백준, 프로그래머스만 했었는데 리트코드의 이점이 상대적으로도 꽤나 많은 것 같다. 이 사이트에서 앞으로 문제풀이를 해보려고 한다. 쉬운 문제더라도 깊게 보면서 풀어보자.