1. Two sum

전체탐색으로 풀면 쉽지만 시간복잡도가 높기 때문에 전체탐색 말고 다른 방법을 써야한다.

 

1. 최초 풀이(전체탐색) : 시간복잡도 O(n^2)

모든 값을 다 순회한다. 단, 순서는 상관없으므로, 순열이 아닌 조합의 경우의 수만큼 탐색한다.

 public static 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;
    }

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

2. 정렬 + 슬라이딩 윈도우를 활용한 풀이 : 시간복잡도 O(n log n)

정렬을 하게되면 기존의 idx값을 갖고있어야 하기 때문에, Node (값, idx) 라는 클래스를 만들고 정렬 조건을 "값 오름차순"으로 해서 풀이함.

    public static class Node implements Comparable<Node> {
        int value, idx;
        Node (int value, int idx) {
            this.value = value;
            this.idx = idx;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }

    public static int[] twoSum1(int[] nums, int target) {
        List<Node> idxValue = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            idxValue.add(new Node(nums[i], i));
        }
        Collections.sort(idxValue);
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int sum = idxValue.get(start).value + idxValue.get(end).value;
            if (sum == target) {
                return new int[] {idxValue.get(start).idx, idxValue.get(end).idx};
            } else if (sum > target) {
                end--;
            } else if (sum < target) {
                start++;
            }
        }
        return null;
    }

 

 

3. HashMap을 사용한 풀이 : O(n)

Map<값, idx>을 만든다.

맵에 원하는 값이 있으면 바로 return하고, 없으면 현재 값도 map에 넣어준다.

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

 

아이디어

• 각 숫자를 순회하면서 "나랑 짝지어서 target을 만들 상대(target - nums[i])가 이미 나왔었나?"를 확인
• 이미 나왔다면 그 상대의 인덱스와 현재 인덱스를 바로 반환
• 안 나왔다면 현재 숫자를 map에 저장해두고 다음으로

이 방법이 왜 인덱스 문제를 자연스럽게 해결하냐면, 정렬을 안 하니까 원래 인덱스가 그대로 유지되기 때문이야. 정렬 방식에서 겪었던 "정렬 전 인덱스를 어떻게 들고 있지"라는 고민 자체가 없어져.

복잡도

• 시간: O(n) — 한 번의 순회
• 공간: O(n) — HashMap