LeetCode 코딩테스트 Two Sum – Array(1)

by

LeetCode는 소프트웨어 엔지니어링 및 코딩 인터뷰 준비를 위한 플랫폼이다. 다양한 프로그래밍 언어로 구현된 코딩 문제가 공하며 알고리즘 능력을 향상시키는데 도움을 준다.

LeetCode에 수 많은 문제 중에 시간을 절약하기 위해 New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time 에서 각 카테고리/유형 별로 추천하는 75개 문제를 풀어본다.

이번 POST에서는 Array문제인 Two Sum 문제를 python으로 풀어보았다.

Leetcode 문제설명

이 문제는 Array 첫번째 문제의 첫번째 예시를 보면 주어진 배열 nums에서 0번 인덱스의 2와 1번 인덱스 7을 선택하면 합이 9가 된다. 따라서 [0, 1]을 반환한다.

해당 문제는 https://leetcode.com/problems/two-sum/에서 확인할 수 있습니다.

솔루션

문제를 보았을때 가장 간단하게 풀수 있는 방법은 2중 for루프를 사용하는 방법으로 아래와 같이 풀었다.

하지만 이 방법은 시간 복잡도가 O(n2)로 runtime이 2509ms로 비효율적이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 배열을 순회하며 모든 가능한 조합을 확인
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                # 두 수의 합이 목표 값과 일치하면 해당 인덱스를 반환
                if nums[i] + nums[j] == target:
                    return [i, j]
leetcode-two-sum

해시맵(HashMap)을 사용하여 문제를 풀면 시간 복잡도를 O(n)으로 개선할 수 있다.

이를 위해 각 요소를 해시 맵에 저장하고 합을 찾을때 해당 요소의 보수(complement)가 해시 맵에 있는지 확인한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 딕셔너리를 사용하여 각 숫자의 인덱스를 저장
        num_indices = {}
        
        for i, num in enumerate(nums):
            # 현재 숫자와 목표 값과의 차이를 계산
            complement = target - num
            
            # 차이가 딕셔너리에 존재하면 해당 인덱스와 현재 인덱스를 반환
            if complement in num_indices:
                return [num_indices[complement], i]
            
            # 차이가 딕셔너리에 없으면 현재 숫자와 인덱스를 딕셔너리에 저장
            num_indices[num] = i

솔루션 설명

  1. num_indices라는 빈 해시 맵을 초기화한다. 이 해시 맵은 각 요소를 키(key)로 사용하고 해당 요소의 인덱스를 값(value)으로 저장한다.
  2. 배열 nums를 순회하면서 각 요소 num와 해당 인덱스 i를 확인한다.
  3. 현재 요소 num와 target에서 현재 요소를 뺀 값(complement)을 계산한다.
  4. complement가 num_indices 해시 맵에 있다면, 이는 이전에 등장한 요소의 보수이므로, 해당 보수의 인덱스와 현재 인덱스 i를 반환한다. 두 요소의 합이 target이 되는 것이므로 문제의 조건을 만족시킨다.
  5. 그렇지 않다면, 현재 요소와 해당 인덱스를 num_indices 해시 맵에 추가한다. 이를 통해 다음에 나올 요소에서 현재 요소의 보수를 찾을 수 있게 된다.

최종적으로는 해시맵(HashMap)을 사용하는 방법으로 2509ms >> 54ms으로 Runtime을 최적화 할 수 있었다.

다음 문제는 Best Time to Buy and Sell Stock 입니다. 읽어주셔서 감사합니다.

LeetCode 코딩테스트 Best Time to Buy and Sell Stock – Array(2)

Leave a Comment