두 수의 합

두 수의 합

문제는 아래와 같습니다.

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

1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
 
Example 1:
Input: nums = [2,7,11,15],
target = 9 Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

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

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

 

사실 배열을 두 번 반복하면서 모든 조합을 더해서 일일이 확인해 보는 브루트 포스 방식으로 문제를 해결하면 굉장히 쉽게 문제를 해결할 수 있습니다. 하지만 브루트 포스 방식의 경우 O(n2)의 시간 복잡도가 나오며 비효율적입니다.

 

Map을 사용해 성능 최적화

이 문제를 최적화해보겠습니다. Map을 사용해서 브루트 포스 방식을 최적화할 생각입니다. 코드로 먼저 살펴봅시다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        Map<Integer, Integer> numsMap = new HashMap<>();

        // 키와 값을 바꿔서 맵에 저장
        for (int i = 0; i < nums.length; i++) {
            numsMap.put(nums[i], i);
        }

        // target에서 첫 번째 수를 뺀 결과를 키로 조회하고 현재 인덱스가 아닌 경우 정답으로 리턴
        for (int i = 0; i < nums.length; i++) {
            if (numsMap.containsKey(target - nums[i]) && i != numsMap.get(target - nums[i])) {
                return new int[]{i, numsMap.get(target - nums[i])};
            }
        }

        // 항상 정답이 존재해서 null 리턴될 일 없음
        return null;
    }
}

Map을 사용해 최적화한 풀이는 아래와 같은 흐름입니다.

1. 제공되는 int 배열의 값을 Map의 Key에 저장하고, 배열의 인덱스를 Map의 Value에 저장합니다.
2. int 배열을 순회하며, 두 수의 합이 목표로 하는 target에서 배열의 값을 먼저 뺍니다.
   다음 뺀 결과를 Map의 Key로 조회해 해당 Value를 통해 두 수의 합을 target으로 만들 값의 인덱스를 얻습니다.
3. 이때 2번에서 현재 인덱스를 정답으로 착각할 수 있기 때문에 예외를 처리해야 합니다.
   만약 배열이 [3, 2, 4]이고 target이 6인 경우 numsMap .get(3)은 0이 되기 때문에 [0, 0]이 마치 정답인 것처럼 착각할 수 있습니다. 따라서 i != numsMap.get(target - nums[i])로 현재 인덱스가 아닌 경우에만 정답으로 간주하고 리턴해야 합니다.

Map의 구현체로 HashMap을 사용했고, Map을 사용했기 때문에 조회에는 O(1)이 걸립니다.

처음 브루트 포스로 풀었을 때 O(n2)였던 시간 복잡도를 Map을 사용하여 O(n)으로 개선했습니다.