LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 숫자가 담긴 배열 nums, 목표 값 target
2. output: 더해서 target을 만들 수 있는 두 값의 인덱스
3. 정확히 하나의 답만 있음
   • 2 <= nums.length <= 104
   • 109 <= nums[i] <= 109
   • 109 <= target <= 109

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

Idea

가장 먼저 생각한 것은 그냥 완전 탐색으로 가능한 쌍을 찾는 것이 었다.

조금 더 발전 시키기 위해, 오직 하나의 답이 무조건 존재한다는 것을 이용하므로 배열을 미리 정렬 후, 투 포인터를 사용하여 가능한 쌍을 찾았다.

하지만, 그럼에도 시간복잡도의 점수가 만족스럽지 않게 나왔고, 정렬을 하지 않고 답을 찾을 수 없을 까 고민하다, Hash로 접근하여 괜찮은 풀이를 완성할 수 있었다.

Solution

1. BruteForce ⭕

   한 쌍씩 모든 경우 비교

   class Solution {
       fun twoSum(nums: IntArray, target: Int): IntArray {
           for (i in 0..nums.size-2) {
               for (j in 1..nums.size-1) {
                   if (nums[i] + nums[j] == target && i != j)
                       return intArrayOf(i, j)
               }
           }
           return intArrayOf(0, 1)
       }
   }
   

   시간 복잡도: 이중 for문 = n^2

   

2. 주어진 배열을 정렬 후, 투 포인터 사용 ⭕

   class Solution {
       data class Data(val idx: Int, val num: Int)
       fun twoSum(nums: IntArray, target: Int): IntArray {
   				// (인덱스와 값)배열 저장 
           var data = mutableListOf<Data>()
           nums.filterIndexed { idx, value -> data.add(Data(idx, value)) }
   				// 배열 정렬
           val sortedData = data.sortedBy { it.num }
           var left = 0
           var right = nums.size - 1
   				// 양 끝에서 투 포인터 탐색
           while (sortedData[left].num + sortedData[right].num != target) {
               if (sortedData[left].num + sortedData[right].num < target) {
                   left++
               } else {
                   right--
               }
           }
           return intArrayOf(sortedData[left].idx, sortedData[right].idx)
       }
   }
   

   시간 복잡도: 정렬 n log n + 투포인터 순회 n = n log n

   

3. hash 사용 ⭕

   특정 숫자 n에 대해 target을 만들 수 있는 값은 정해져 있음 → hash에 찾는 값 저장

   ex) idx 1에 값 2, target 7 → hash[5] = 1

   class Solution {
       fun twoSum(nums: IntArray, target: Int): IntArray {
           val map = mutableMapOf<Int, Int>()
           nums.forEachIndexed { idx, value ->
               val tmp = target - value // target을 위해 찾아야 하는 값(짝)
               if (map.containsKey(value)) { // 짝이 저장되어 있는 경우
                   return intArrayOf(map[value]!!, idx)
               } else { // 짝이 아직 저장 안된 경우
                   map[tmp] = idx
               }
           }
           return intArrayOf(0, 1)
       }
   }
   

   시간 복잡도: 전체 순회 = n

   

Point

1. 주어진 배열에서 특정 조건을 만족하는 한쌍의 값 찾기

   ⇒ Hash 사용