[2주차] 1. Two Sum

https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150 

Two Sum - LeetCode

---

📝 문제

1차원 정수배열 nums 와 정수 target 이 주어진다.

nums 원소 중 두 수의 합이 target이 되는 인덱스를 배열로 반환하라. 조건에 맞는 인덱스 배열은 단 하나만 존재한다.

 

🎈 풀이

가장 먼저 떠올릴 수 있는 알고리즘은 완전탐색일 것이다.

시간복잡도: O(n^2)

공간복잡도: O(1)

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

O(n^2) 시간으로 해결하였다.

 

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

시간복잡도를 줄이려고 수 시간동안 머리를 싸맸으나 결국 해결하지 못했다.

마지막으로 시도한 코드는 다음과 같다.

 

실패한 코드

public int[] twoSum(int[] nums, int target) {
    Node[] nodes = new Node[nums.length];
    for (int i=0; i<nums.length; i++) {
        nodes[i] = new Node(nums[i], i);
    }
    nodes = Arrays.stream(nodes)
                .sorted(Comparator.comparingInt(node -> node.data))
                .toArray(Node[]::new);

    // 2 3 3
    int j = 1;
    while (j < nodes.length && nodes[0].data + nodes[j].data < target) {
        j++;
    }

    for (int i=0; i<j; i++) {
        if (nodes[i].data + nodes[j].data == target) {
            return new int[] {Math.max(nodes[i].idx, nodes[j].idx), Math.min(nodes[i].idx, nodes[j].idx)};
        }
    }

    return null;
}

private class Node {
    int data;
    int idx;

    Node(int data, int idx) {
        this.data = data;
        this.idx = idx;
    }
}

 

정렬을 이용하기 위해 새로운 Node를 선언했다. 정렬하면 index가 흐트러지기 때문이다.

정렬 후, 투 포인터를 사용하려고 하였으나, 조건을 어떻게 세워도 O(n^2) 시간을 개선할 수 없었다.

정확히 target을 찾아야 하기 때문에 포인터를 이동시키더라도, 두 수의 합이 target 이상이 되면 포인터를 뒤로 이동시켜야 하기 때문이다.

 

📈 타 솔루션 참고

시간복잡도: O(n)

공간복잡도: O(n)

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

    return null;
}

HashMap 을 사용한 모습이다. key는 각 원소의 값, value는 인덱스를 의미한다.

nums 를 순회하며 만약 현재 원소의 target 의 차가 맵에 들어있으면 답을 찾은것을 의미한다.

그 외에는 값과 인덱스를 map에 저장한다.