1. Two Sum

문제 : https://leetcode.com/problems/two-sum/

단순한 해결법 : 하나의 숫자를 선택하고 나머지 숫자들을 돌면서 합이 target이 되는 숫자를 찾는다.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] result = new int[2];

        int arrayLastIndex = nums.length - 1;
        for (int firstNumIndex = 0; firstNumIndex <= arrayLastIndex - 1; firstNumIndex++) {
            for (int secondNumIndex = firstNumIndex + 1; secondNumIndex <= arrayLastIndex; secondNumIndex++) {
                if (nums[firstNumIndex] + nums[secondNumIndex] == target) {
                    result[0] = firstNumIndex;
                    result[1] = secondNumIndex;
                    break;
                }
            }
        }

        return result;
    }
}
Java
복사

하지만 위의 솔루션은 O(n^2)의 복잡도를 갖는다.

이 복잡도보다 낮은 솔루션은 무엇이 있을까?

그래서 생각해 낸 것이 아래의 솔루션이다.

public class Solution {
    public int[] twoSum(int[] nums, int target) {

        int[] result = new int[2];

        Map<Integer, List<Integer>> numberAndIndexMap = new HashMap<>();

        for (int indexOfNum = 0; indexOfNum < nums.length; indexOfNum++) {
            if (numberAndIndexMap.containsKey(nums[indexOfNum])) {
                List<Integer> indicesOfNum = numberAndIndexMap.get(nums[indexOfNum]);
                indicesOfNum.add(indexOfNum);
            } else {
                numberAndIndexMap.put(nums[indexOfNum], new ArrayList<>(List.of(indexOfNum)));
            }
        }

        for (int indexOfNum = 0; indexOfNum < nums.length; indexOfNum++) {
            int theOtherNum = target - nums[indexOfNum];
            if (numberAndIndexMap.containsKey(theOtherNum)) {
                List<Integer> indicesOfNum = numberAndIndexMap.get(theOtherNum);
                if (indicesOfNum.size() == 1 && indicesOfNum.getFirst() != indexOfNum) {
                    result[0] = indexOfNum;
                    result[1] = indicesOfNum.getFirst();
                    break;
                }
                if (indicesOfNum.size() == 2) {
                    result[0] = indexOfNum;
                    final int finalIndexOfNum = indexOfNum;
                    result[1] = indicesOfNum.stream()
                            .filter(index -> index != finalIndexOfNum)
                            .findFirst()
                            .orElseThrow(() -> new IllegalArgumentException("조건에 맞는 숫자가 없습니다."));
                    break;
                }
            }
        }

        return result;
    }
}
Java
복사

HashMap에 숫자와 해당 숫자의 인덱스들을 모두 저장해 놓는다.

그리고 숫자를 하나씩 돌면서 다른 숫자의 인덱스(돌고 있는 인덱스와 달라야 한다.)를 찾는다.

위 코드의 복잡도는 O(N)이지만, 이보다 더 낮은 해법이 있다고 해서 찾아보았다.

해당 코드는 아래와 같다.

public class Solution {
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> numberAndIndexMap = new HashMap<>();

        for (int indexOfNum = 0; indexOfNum < nums.length; indexOfNum++) {
            int theOtherNum = target - nums[indexOfNum];
            if (numberAndIndexMap.containsKey(theOtherNum)) {
                return new int[]{indexOfNum, numberAndIndexMap.get(theOtherNum)};
            } else {
                numberAndIndexMap.put(nums[indexOfNum], indexOfNum);
            }
        }

        return new int[]{};
    }
}
Java
복사

간결하다.

숫자를 하나씩 돌면서 차례가 지나간 앞의 숫자중에 정답이 있었는지 찾는다.

없으면 돌고 있는 현재 숫자를 HashMap에 저장한다.