[파이썬] TwoSum 해시로 풀기

Two Sum 문제 해쉬로 풀어보기

https://leetcode.com/problems/two-sum/description/

 

해시를 사용하여 풀 수 있는 코딩테스트 문제 중 하나는 "두 수의 합 (Two Sum)" 문제입니다. 이 문제는 매우 유명하며, 해시맵을 사용하면 효율적으로 해결할 수 있습니다.

문제 설명

주어진 배열 nums와 정수 target이 있을 때, 배열에서 두 수를 더해서 target이 되는 두 개의 인덱스를 찾으시오. 각 입력에 정확히 하나의 해답이 있다고 가정하며, 같은 요소를 두 번 사용할 수 없습니다.

예제:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

이 경우, nums[0] + nums[1] = 2 + 7 = 9이므로 답은 [0, 1]입니다.

문제 풀이

이 문제를 해결하기 위해 해시맵을 사용할 수 있습니다. 해시맵을 사용하면 배열을 한 번만 순회하면서 문제를 해결할 수 있습니다.

알고리즘

1. 빈 해시맵을 생성합니다.
2. 배열을 순회하면서 각 요소에 대해 target에서 현재 요소를 뺀 값을 계산합니다.
3. 이 값이 해시맵에 존재하는지 확인합니다.
   • 존재하면, 그 값과 현재 요소의 인덱스를 반환합니다.
   • 존재하지 않으면, 현재 요소와 그 인덱스를 해시맵에 추가합니다.
4. 배열을 끝까지 순회했을 때 답이 없다면, 답이 없다고 판단합니다.

코드 구현 (파이썬)

def two_sum(nums, target):
    hash_map = {}  # 값과 인덱스를 저장할 해시맵

    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i

    return None  # 답이 없는 경우

# 예제 실행
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # 출력: [0, 1]

코드 설명

• hash_map은 각 요소의 값을 키로, 그 요소의 인덱스를 값으로 저장합니다.
• for 루프를 통해 배열 nums를 순회하면서 각 요소 num에 대해 target - num이 hash_map에 있는지 확인합니다.
• complement가 해시맵에 존재하면, 현재 인덱스 i와 complement의 인덱스를 반환합니다.
• 존재하지 않으면, 현재 요소와 그 인덱스를 해시맵에 추가합니다.

이 알고리즘은 시간 복잡도가 O(n)으로, 매우 효율적입니다. 배열을 한 번만 순회하면서 문제를 해결할 수 있기 때문입니다.

---

이번엔 다른 문제를 해시로 풀어보겠습니다.

Next Greater Element 스택, 해시로 풀어보기

https://leetcode.com/problems/next-greater-element-i/

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        hash_map = {}
        
        for num in nums2:
            while stack and stack[-1] < num:
                top = stack.pop()
                hash_map[top] = num
            stack.append(num)
            #아니면
            hash_map[stack[-1]] = -1
            
        ans = [hash_map[num] for num in nums1]
        return ans

풀긴 풀었는데 너무 어려웠습니다. 구현하고 나면 쉬워보이지만 구현하기 까지 숫자들을 이리저리 써가며 나열하는 과정이 머리속을 지저분하게 만듭니다.

여기서 stack을 사용하는 이유는 오큰수, 즉 나보다 오른쪽으로 더 큰 수를 찾으려고 하기 때문에 num의 이전 값을 append한 stack[-1]과 num과 비교할 수 있기 때문입니다. 또 자신보다 큰 수를 찾았을 때 pop을 하여 stack을 비어있게 만듦으로써 while조건문을 탈출할 수 있게 합니다. hash를 사용하는 이유는 자신의 값과 자신보다 큰 값을 매칭하기 쉽게 하기 위해서입니다. hash를 사용하지 않고 매칭을 하려면 for문을 두 번 도는 수밖에 없겠지요.