Two Sum

문제

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

---

풀이

여러 숫자들이 나열된 배열에서 2개의 숫자를 더했을 때, target과 같은 2 숫자의 인덱스를 출력해야 한다.

1. 이중 for문을 사용하여 브루트포스를 진행한다.
2. 이중 for문으로 찾은 2개의 숫자의 합이 target과 같다면 result 배열에 넣고 break 한다.

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

33ms

제일 간단하고 확실하지만 모든 경우의 수를 확인한다는 점에서 느리다.

---

O(1)을 사용하기

시간복잡도 O(1)이라면 바로.. Hash를 사용하는 것이다.
해당 코드에서 HashMap을 사용해서 구현할 수 있다.

어떻게 활용할 수 있을까?

1. 현재 target을 완성하는 2개의 숫자를 찾고 있다면, 역으로 target-x 인 y를 찾는 것이다.
2. HashMap에 nums 배열의 숫자와 인덱스를 넣는다.
3. 그 y를 찾는 과정에서 HashMap을 사용하면 된다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        int [] answer = {};
        
        //HashMap에 넣는 과정
        for (int i=0; i<nums.length; i++) {
            hm.put(nums[i], i);
        }
		
        
        for (int i=0; i<nums.length; i++) {
            int minus = target - nums[i]; // x를 구하는 과정
            if (hm.containsKey(minus)) { //y를 찾는 과정
                int index = hm.get(minus);
                if (index == i) continue; // 동일한 인덱스는 포함하지 않는다.
                answer = i < index ? new int[] {i, index} : new int[] {index, i}; //인덱스를 올바르게 정렬
                break;
            }
        }
        return answer;
    }
}

4ms !!

역시 Hash는 .. 굉장히 빠른 속도를 자랑한다.

하지만 여기서 더 줄일 수 있다면?

---

최대한 하나의 반복문에서 처리하기

현재 nums 배열의 값을 HashMap에 넣는 과정과 HashMap에서 값을 찾는 과정이 분리되어 있다.

이것을 하나의 반복문에서 처리해보자!!

배열을 처음부터 순회할 때, target-x인 값이 HashMap에 있는 지 확인하고
있으면 바로 반환, 없다면 새로 넣는다.

어차피 숫자 2개로 target을 만들어야 하기 때문에 가능하다.

만약 현재 nums 배열이 [3,2,4] 이고, target이 6일 때를 생각해보자.

1. 3를 확인할 때면 6-3=3 은 HashMap에 없기 때문에 HashMap에 3를 넣게 된다.

   HashMap : <3,0>

2. 2를 확인할 때면 6-2=4 도 아직 없어서 2를 넣는다.

   HashMap : <3,0> <2,1>

3. 4를 확인할 때면 6-4=2 가 존재하기 때문에, 해당 값을 가져온다.

   HashMap : <3,0> *<2,1>*

그렇다면 최종적으로 HashMap에서 가져오는 값(2)은 현재 보고 있는 값(4)보다 전 인덱스에 위치했기 때문에 그대로 넣으면 된다.

(출력값에 인덱스 순서가 중요한 줄 알았지만 상관 없었다...)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        int [] answer = {};
        for (int i=0; i<nums.length; i++) {
            int minus = target - nums[i];
            if (hm.containsKey(minus)) {
                answer = new int[] {i, hm.get(minus)};
                break;
            } else hm.put(nums[i], i);
        }
        return answer; //출력값이 꼭 있기 때문에 null 처리
    }
}

2ms !!

굉장히 많이 줄였다.

---

아니 여기서 더 줄일 수 있다고?

이중 for문을 사용했지만, 배열 내에 인덱스로 사용하는 것이 아닌
배열 내에서 확인하는 숫자들의 거리를 조절하도록 사용하였다.

[1,2,3,4,5] 가 있다면

i = 1
<1,2> -> <2,3> -> <3,4> -> <4,5>

i = 2
<1,3> -> <2,4> -> <3,5>

i = 3
<1,4> -> <2,5>

i = 4
<1,5>

결국에는 어떤 공식이 보인다. 바로 조합(Combination)!

(1,2) 과 (2,1)를 같다고 보기 때문에, 조합의 원리를 통해서 풀어도 가능했다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i=1; i<nums.length; i++) { // 현재 확인하는 인덱스에서 i만큼 전에 위치한 값
            for (int j=i; j<nums.length; j++) { // 현재 확인하는 인덱스
                if (nums[j] + nums[j-i] == target) {
                    return new int [] {j-i, j};
                }
            }
        }
        return null;
    }
}

0ms

그냥 순식간이다... 🫨