Two Sum (Dictionary)

LeetCode의 첫 번째 문제인 Two Sum이다.

Two Sum - LeetCode

문제 자체는 간단하다. 정수 배열과 목푯값이 주어지고 해당 배열에서 두 수를 꺼내서 목푯값을 만들 수 있을 때 배열에서 두 수의 인덱스를 리스트로 반환하는 것이다. 예를 들어 [1, 2, 3, 4, 5]가 있고 6을 만들어야 할 때 [0, 4]를 반환하면 되는 것이다.

 

문제에서는 배열 내에 목푯값을 만들 수 있는 최소한 한 쌍의 정수가 존재한다고 명시하고 있다. 그렇기 때문에 목푯값을 만들 수 있는 조합을 발견하지 못했을 때 예외 처리는 구현하지 않아도 된다.

 

가장 먼저 떠오르는 생각은 처음 인덱스와 그다음 인덱스부터 하나하나 비교해서 합해보면서 목푯값을 만들 수 있는 쌍을 찾는 것이다. 실제로 내가 약 2년 전에 풀었던 Java 코드에서는 그런 방식을 사용하고 있다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++) {
            for(int j=i+1;j<nums.length;j++) {
                if(nums[i] + nums[j] == target) {
                    return new int[] {i,j};
                }
            }
        }
        return null;
    }
}

2018년 12월의 나는 이상함을 못 느낀 건지 모르겠지만 일단 2중 반복문이 사용되고 있다는 점에서 뭔가 잘못됐다는 점을 알아차렸어야 했다. 실제로 이 코드의 속도는 40ms로 아예 랭킹에 표시조차 안 되는 최악의 성능이었다. 사실 지금 다시 본다고 해도 이렇게 일일이 비교하는 것 말고는 별다른 풀이가 없지 않나? 싶지만 알고리즘 책을 읽으면서 다시 공부해보니 절대로 그렇지 않다는 것을 알 수 있었다.

 

이 문제는 여러 가지 해결 방법이 있지만 책에서 설명하는 내용 위주로 적어보겠다. 첫 번째로 제시되는 방법은 파이썬의 슬라이싱과 in 메서드를 사용하는 것이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index, num in enumerate(nums):
            if target-num in nums[index+1:]:
                return [index, nums.index(target-num,index+1)]

파이썬의 in 연산자는 O(n) 복잡도를 가지기 때문에 얼핏 보면 O(n^2)의 시간 복잡도가 아닌가? 생각할 수 있지만 파이썬의 in 연산자는 매번 값을 비교하는 것보다 빨리 실행된다고 한다. 시간 복잡도에서는 생략된 상수항이 영향을 미친다고 하는데 Java로 제출한 풀이와 동일한 2중 반복문 코드를 파이썬으로 제출해도 큰 시간 차이가 없는 걸 보면 언어별로 실행 환경의 차이거나 평가 기준이 좀 다른 것 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index = 0
        while index < len(nums):
            inner_index = index + 1
            while inner_index < len(nums):
                if nums[index] + nums[inner_index] == target:
                    return [index, inner_index]
                
                inner_index += 1
            
            index += 1

아무튼 이렇게 직접 반복하는 것보다는 뭔가 자료구조를 사용해서 해결할 순 없을까? 이제 두 번째 방법으로 해싱을 사용하는 사전 자료형을 시도해 볼 수 있다. 문제에서 주어지는 정수 배열에는 중복된 정수가 담길 수 있기 때문에 이를 어떻게 구분해야 하나 싶지만 배열의 처음부터 하나하나 비교하면서 인덱스를 기억하면 헷갈리지 않을 수 있다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numbers = {}
        for index, num in enumerate(nums):
            numbers[num] = index
            
        for index, num in enumerate(nums):
            if target-num in numbers and numbers[target-num] != index:
                return [index, numbers[target-num]]

먼저 정수 배열을 하나하나 탐색하면서 정수 값을 키로, 배열에서 해당 정수 값의 위치를 값으로 하는 사전 자료형을 생성한다. 그리고 배열을 탐색하면서 목푯값을 만들기 위해 필요한 값, 예를 들어 9를 만들어야 하는데 현재 배열에서 탐색하는 값이 2라면 7이 사전에 존재하는지 탐색한다. 그리고 배열에서 그 정수 7이 어디에 위치하는지 인덱스를 참조하여 현재 탐색하고 있는 값은 아닌지 확인한다. 7과 2는 확연히 다른데 왜 굳이 이렇게 비교하는 것일까?

Input: nums = [3,3], target = 6
Output: [0,1]

이는 문제에서 테스트 케이스로 주어진 위와 같은 상황 때문이다. 배열의 모든 정수가 동일하고 같은 정수끼리 더해야 목푯값을 만들 수 있을 때 같은 정수, 정확히는 현재 탐색하고 있는 정수를 계산에 활용하면 안 되기 때문에 각 정수마다 배열에서의 위치를 기억해두는 것이다. 사전은 고유한 키에 대해서 값을 유지하기 때문에 nums 배열을 탐색하며 사전 자료형을 구축할 때 정수 3(키)은 0(값)에서 1(값)로 갱신된다. 그리고 첫 번째 정수(인덱스 0)부터 탐색할 때 목푯값을 만들기 위해 필요한 정수(3)가 사전에 존재하는지, 즉 이 주어진 정수 배열에 존재하는지 확인한 후(target-num in numbers) 지금 탐색하는 정수(인덱스 0)랑은 다른 정수(인덱스 1)인지 확인하여 반환하는 것이다.

Input: nums = [1,6,3,4,3], target = 6
Output: [2,4]

위의 예제에서 사전 자료형을 구축하면 {1:0, 6:1, 3:4, 4:3}처럼 생성될 것이다(키-값). 3번째 요소(인덱스 2)인 3에서 6을 만들기 위해 3 값을 탐색할 때 사전 자료형의 3은 4 값을 가지고 때문에 인덱스 4의 3이며 이는 현재 탐색하고 있는 인덱스 2의 3이 아니면서도 목푯값을 만들 수 있는 정수라고 판단하여 [2, 4]를 반환하는 것이다.

실행 결과는 그렇게 큰 이득은 없었지만 사전 자료형 활용 연습의 계기가 되었다. Python에서는 별 차이가 없었지만 Java로 제출한 코드의 상위권(0ms)에서는 이와 비슷한 로직으로 구현된 것을 볼 수 있었다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numMap.containsKey(target - nums[i])) {
                int[] answerPair = {numMap.get(target - nums[i]), i};
                return answerPair;
            } else {
                numMap.put(nums[i], i);
            }
        }
        return null;
    }
}

사전 자료형, 그 중에서도 해싱을 사용한 HashMap을 사용했기 때문에 높은 성능을 낼 수 있는 모양이다.

 

 

책에서도 이 문제는 쉬워 보이지만 자칫 최적화를 놓치기 쉽기 때문에 면접에서도 자주 언급되는 문제라고 한다. 특히 목푯값에서 현재 값을 뺀 값, 즉 목푯값을 만들기 위해 필요한 값이 배열에 포함되어 있는지 탐색한다는 아이디어가 참 인상 깊었다.