[Leetcode] 1번 - 두 수의 합

1. 문제 파악

1. 문제 링크: https://leetcode.com/problems/two-sum/description/
2. 문제 정의: 배열의 요소중 두개의 합이 target인 인덱스 두개를 반환해라. 답은 하나이고 반환하는 인덱스의 순서는 상관없다. 단, 배열의 동일한 요소의 합은 포함되지않는다.
3. 문제의 제약 파악 (입력값 크기, 상수 조건) 
   • 2 <= nums.length <= 10000: 시간복잡도가 O(NlogN) 이내여야 통과하는데 안전하다.

---

2. 문제 풀이

1. 브루트 포스로 문제 풀이 도출

1. 배열을 순회하면서 순차적으로 요소 하나를 지정
2. 1번에서 지정한 요소를 제외하고, 배열을 순회하면서 순차적으로 나머지 요소를 지정
3. 지정한 두 요소의 합이 target과 동일한지 확인
4. 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};
// ...

 

두개의 요소를 찾기 위해서 이중 순회를 해야하므로 시간복잡도는 O(N^2)이다.

 

2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?

시간복잡도 내로 풀기 위해서는 O(NlogN)이나 O(N)으로 풀어야한다.

 

기준점으로 지정할 요소를 순회하는것은 O(N)이 걸린다. 그러면 기준점인 요소의 합이 target인 요소를 O(1) 내에 찾을수 있을까? 생각해보았다.

 

이때 HashMap에서 입출력하는 평균 시간 복잡도는 O(1)이므로 해당 자료구조를 사용해서 해결방안을 도출해보았다.

1. HashMap에 배열 요소를 모두 입력한다.
2. 기준점으로 지정할 배열을 순회하면서 HashMap에서 target - 기준점 요소의 값을 출력한다.
3. 만일 값이 있다면 두 배열의 요소를 반환하고, 없다면 2번을 반복한다.

 

4. 입출력 케이스 도출 및 문제 풀이 도출 확인

• 일반 케이스
  • Input: nums = [2,7,11,15], target = 9
  • Output: [0,1]
• 엣지 케이스
  • Input: nums = [3,3], target = 6
  • Output: [0,1]

문제에서도 나와있지만, 엣지 케이스와 같이 동일한 요소(0과 0인덱스)의 합은 포함되지 않는다. 그외에 특이 사항은 없으므로 핵심 풀이 로직을 따라서 코드로 구현해볼것이다.

 

5. 코드 구현

위의 핵심 문제 풀이 도출에서의 로직으로 코드로 구현하면 다음과 같다. 주의해야될 점은 배열의 동일한 요소의 합은 포함되지않으므로, 따라서 인덱스가 동일하면 안된다. 해당 코드의 실행 시간은 4ms이 걸렸다.

public int[] twoSum(int[] nums, int target) {  
    int n = nums.length;  

    // 1. `HashMap`에 배열 요소를 모두 입력한다.
    HashMap<Integer, Integer> hashMap = new HashMap<>(); // 인덱스가 반환할 데이터이므로, 요소 값을 key로 요소 인덱슬르 value로 저장  
    for (int i = 0; i < n; i++) {  
        hashMap.put(nums[i], i);  
    }  

    for (int i = 0; i < n; i++) {  
        // 2. 기준점으로 지정할 배열을 순회하면서 `HashMap`에서 `target - 기준점 요소의 값`을 출력한다.
        Integer idx = hashMap.get(target - nums[i]);  
        if (idx != null && idx != i) { // 동일한 배열 요소는 포함시키지 않는다.
            return new int[]{i, idx}; // 2. 만일 값이 있다면 두 배열의 요소를 반환하고, 없다면 2번을 반복한다.
        }  
    }  
    return new int[]{}; // 문제의 답은 항상 하나 존재  
}

 

6. 최적화

위의 코드에서 연산을 줄일 가능성이 있는 부분은 HashMap의 입출력 횟수이다.

 

그다음 "굳이 모든 값을 먼저 HashMap에 다 저장할 필요가 있을까?"라고 질문을 던졌다.

 

결론은 HashMap에서 출력을 먼저하고 입력을 후에 하면, 기준점 이전의 배열의 요소에 대해서 현재 지정한 요소와의 합이 target인지 확인이 가능하다.

기준점: 2
Array: [2, 7, 11, 15]
HashMap: []

기준점: 7
Array: [2, 7, 11, 15]
HashMap: [2:0]

기준점: 11
Array: [2, 7, 11, 15]
HashMap: [2:0, 7:1]

 

최적화를 수행한 코드는 다음과 같다. 실행 시간은 2ms가 나왔다.

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    HashMap<Integer, Integer> hashMap = new HashMap<>(); // 인덱스가 반환할 데이터이므로, 요소 값을 key로 요소 인덱슬르 value로 저장
    for (int i = 0; i < n; i++) {
        // 값을 먼저 출력하고 입력하므로 동일한 인덱스 값의 합은 경우의 수에서 제거
        Integer idx = hashMap.get(target - nums[i]);
        if (idx != null) {
            return new int[]{i, idx};
        }
        hashMap.put(nums[i], i); 
    }
    return new int[]{}; // 문제의 답은 항상 하나 존재
}

 

5. 복잡도

• 시간 복잡도
  • 배열 순회: O(N)
  • 해시테이블 입력: O(1)
  • 해시테이블 출력: O(1)
  • 최종 시간복잡도: 배열 순회 x 해시테이블 입력 x 해시테이블 출력 = O(N)
• 공간 복잡도
  • 추가 공간은 해시 테이블에 배열의 요소들을 저장하기 때문에 O(N)이다.