Leetcode 1. Two Sum - Dart, Python

Leetcode 1 문제 보기

 

1. 문제 이해하기

정수가 담긴 리스트 nums가 있다.

이때 리스트의 두 원소를 더해 정수인 target을 만족할 경우, 해당 두 원소의 인덱스의 조합을 출력하라.

하나의 원소를 중복 사용할 수 없으며, 각 test case의 정답은 딱 하나 존재한다.

 

2. 아이디어 구상

문제를 읽고 가장 먼저 떠오른 생각은 투 포인터를 이용해볼까하는 생각이었다.

그러나 조금만 생각해보면 투 포인터를 이용하기가 쉽지는 않다는 점을 알 수 있다.

투 포인터를 이용하려면 리스트 nums가 정렬되어야한다.

그러나 본 문제에서는 원소 그 자체가 아닌 인덱스를 출력해야하므로, 무턱대고 정렬할 경우 문제가 생길 수 있다.

때문에 정 투 포인터를 이용하고 싶다면, (value, index) 쌍으로 리스트를 재정의하고 정렬 후 시도해볼 수는 있겠다.

하지만 좀 더 깔끔하고 효율적인 방법을 고민해보자.

 

마찬가지로 키 포인트는 index다.

문제에서 다루는 것은 value(원소의 값)이나, 결국 구해야하는 것은 index다.

그러니 원소의 값을 key로 하고 인덱스를 value로 하는 Hashmap을 이용해보는 것은 어떨까?

[2, 7, 11, 15]인 test case의 Hashmap을 살펴보자.

 

By Mesotes

 

(key, value) = (원소값, 인덱스)로 Hashmap을 만들고 enumerate(nums)를 탐색하면서, target - num이 Hashmap에 존재할 경우 그 때의 index 쌍을 출력할 수 있겠다. 이렇게 생각해보니, 1.Hashmap을 만드는 과정과 2.index쌍을 찾는 과정을 하나의 반복문 안에서 해결할 수 있을 것 같다.

 

이 때의 시간복잡도는 어떻게 될까?

n = len(nums)라 할 경우, nums를 순차 탐색하면서 Hashmap을 만들고 index쌍을 찾기 때문에,

최종적으로 Time Complexity ~ O(n)일 것이다.

 

3. 풀이

<Python 풀이>

{원소값, 인덱스}를 담을 nums_map을 선언한다.

nums_map = collections.defaultdict(int)

 

enumerate(nums)를 탐색하며 target - num이 Hashmap에 존재하는지 확인하는 작업과 Hashmap을 만드는 작업을 진행한다.

for i, v in enumerate(nums):
    val = target - v
    if val in nums_map:
        return [nums_map[val], i]
    nums_map[v] = i

 

전체 코드는 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = collections.defaultdict(int)
        for i, v in enumerate(nums):
            val = target - v
            if val in nums_map:
                return [nums_map[val], i]
            nums_map[v] = i

 

<Dart 풀이>

Dart의 풀이도 유사한 흐름으로 진행된다.
우선 {원소값, 인덱스}를 담을 numsMap을 선언한다.

Map<int, int> numsMap = new Map();

 

for문을 돌며 numsMap이 target - num 을 가지고 있다면 정답을 출력하고 그렇지 않다면 num과 해당 index를 map에 추가해준다.

for (int i = 0; i < nums.length; i++) {
    if (numsMap.containsKey(target - nums[i])) {
        return [numsMap[target - nums[i]]!, i];
    }
    numsMap[nums[i]] = i;
}

이때 if문 안의 return 값에 주목하자.

numsMap[target - nums[i]]!

저 느낌표가 없으면 Dart는 다음과 같은 에러를 내뱉는다.

Error: A value of type 'int?' can't be assigned to a variable of type 'int' because 'int?' is nullable and 'int' isn't.

이는 함수의 return값으로 int를 원소로 하는 list가 되야함에도 numsMap[target - nums[i]]의 값이 null이 올 수도 있기 때문에 발생한 에러다. Dart는 null safety language다. 때문에 이와 같은 상황에서는 뒤에 ’?.‘를 불여 해당 값이 null이 아닐 경우 작업을 계속 진행하거나, ‘!’를 통해 해당 값이 null이 될 수 없음을 명시해야한다.

‘?.’와 달리 ‘!’는 null check를 수행하지 않고 값이 null이 아닐 것이라 가정하고 작업을 진행한다. 때문에 null check을 위한 추가적인 연산시간과 메모리 사용에 있어 이득이다. 그러나 값이 확실히 null이 아니라는 보장이 있지 않은 한, runtime 시 오류가 발생하는 것을 막기 위해 ‘!’ 사용은 지양해야한다.

 

 

전체 코드는 다음과 같다.

마지막에 return [] 구문도 위와 비슷한 논리로 인해 추가된 것이다. 즉, twoSum() 함수는 List<int>를 출력해야하며 null이 될 수 없다. 따라서 for문 바깥에 null이 아닌 값을 어떻게든 default로 출력하도록 해야한다.

class Solution {
  List<int> twoSum(List<int> nums, int target) {
    Map<int, int> numsMap = new Map();
    for (int i = 0; i < nums.length; i++) {
        if (numsMap.containsKey(target - nums[i])) {
            return [numsMap[target - nums[i]]!, i];
        }
        numsMap[nums[i]] = i;
    }
    return [];
  }
}

 

---

Leetcode 1. Two Sum

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

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다