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

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라

내 풀이

//270ms 38.1MB
fun twoSum(nums: IntArray, target: Int): IntArray {
    for (i in nums.indices) {
        for (j in nums.indices) {
            if (nums[i] + nums[j] == target && i!=j) {
                return intArrayOf(i, j)
            }
        }
    }
    throw intArrayOf()
}

가장 기본적으로 2중 for문을 이용하여 덧셈을 하는 방식을 이용하여 풀었다.

위와 같이 계산하면 2중 for문으로 배열을 순회하기 때문에 O(n^2)의 시간 복잡도가 나오게 된다.

map을 이용한 풀이

//190ms 38.5MB
fun twoSum(nums: IntArray, target: Int): IntArray {
    val nums_map = mutableMapOf<Int, Int>()

    for (i in nums.indices) {
        nums_map[nums[i]] = i
    }

    for (i in nums.indices) {
        if (target - nums[i] in nums_map && i != nums_map[target - nums[i]]) {
            return intArrayOf(i, nums_map[target - nums[i]]!!)
        }
    }
    throw IllegalArgumentException("No two sum solution")
}

찾아본 풀이에서는 map을 이용하여 문제를 해결하였다.

map에서 조회하는 경우 O(1)의 시간복잡도를 갖기 때문에 전체적으로는 O(n)의 시간복잡도로 성능향상이 있을 것이다.
실제 leetcode에서도 270ms -> 190ms 로의 성능향상이 있다.

아이디어는 key-value를 value-index로 맵을 만들고,

타겟에서 value를 뺀 값이 맵 안에 존재하고 그 값이 이번 i가 아니라면 그 index들을 리턴하는 방식이다.

조금 말이 복잡한데 , 직관적으로 설명할 수 있는 말을 생각해보자…