LeetCode - Two Sum

문제 링크 : https://leetcode.com/problems/two-sum/

난이도 : Easy

---

문제 풀이 :

nums 배열에서 target을 만들 수 있는 두 개의 숫자 조합을 찾아 인덱스를 IntArray로 반환하는 문제이다.

두 숫자를 각각 A, B라 하고 두 숫자를 합쳤을 때 나오는 값을 C라고 하자.

그럼 A+B=C 이다.

A를 선택했을 때, C를 만들 수 있는 숫자 B는 C-A로 구할 수 있다.

그렇다면, A를 선택했을 때 나머지 숫자들 중 B가 존재하는지 여부를 알고 그 B의 위치를 알면 답을 구할 수 있다.

두 개의 for-loop을 사용하여 풀 수 있지만, 시간복잡도를 낮추기 위해 HashMap 자료구조를 사용한다.

HashMap의 Key에 숫자를, Value에 그 숫자의 위치를 저장하자.

그리고 nums를 순회하면서 target - nums[i] 의 값이 HashMap에 있는지 파악하고 있다면 그 위치를 획득하여 반환하자.

---

소스 코드 :

class TwoSum {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int, Int>()

        for(i in nums.indices) {
            val complement = target - nums[i]

            if(map.containsKey(complement)) {
                return intArrayOf(map[complement]!!, i)
            }

            map[nums[i]] = i
        }

        throw IllegalArgumentException("No two sum solution")
    }
}

---

후기 : 

위의 소스 코드는 문제를 푼 후 Solution에서 제시하는 소스코드를 참고하여 다시 작성 한 것이다.

문제 풀이는 맞았으나, 수행시간에서 차이가 났다.

어려운 풀이는 아니지만 풀이를 잘 구현하는 방법을 보고 배울 필요가 있는 것 같다.