[LeetCode] 1. Two Sum

풀이 언어 : Java, Kotlin

내가 푼 시간복잡도 : O(n^2) -> O(n)

 

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

처음으로 풀어본 LeetCode 문제

문제를 봤을 때, 이중 for 문을 사용하면 금방 해결할 수 있어 보였지만, 시간복잡도 O(n^2) 밑으로 도전해보라는 것이 마음에 결렸다. 프로그래머스에서 다른 사람의 풀이를 보다보면 나오는 재귀함수를 써보고자 했다.

 

나의 풀이

public class Solution {

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int b = sum(i, i, nums, target);
            if (b > 0) {
                return new int[]{i, b};
            }
        }
        return null;
    }

    private int sum(int position, int current, int[] nums, int target) {
        if (current >= nums.length)
            return 0;

        if (position != current) {
            if (nums[position] + nums[current] == target)
                return current;
            else {
                return 0;
            }
        } else {
            return sum(position, position+1, nums, target);
        }
    }
}

이 코드로 분명 통과는 됐으나, 시간복잡도 면에서 굉장히 나쁘게 나왔다. 일단 이중 for 문을 사용하지 않았으니 괜찮겠지 ? 했지만... 재귀함수에 대해서 더 찾아보니 재귀함수 역시 O(n)이다. 결국은 for 문 안에 재귀함수를 사용했기 때문에 O(n^2) 이 된 것이다.

 

다른 사람의 풀이

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length; i++){
            if(map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{0, 1};
    }
}

이 문제의 Keyword 는 HashMap 이다. 

HashMap 의 get, put, remove, containsKey 모두 O(1) 의 시간복잡도를 가진다. 그래서 위의 시간복잡도는 O(n) + O(1) 이기 때문에 O(n) 이 된다.

 

Kotlin 으로 재도전

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()
        // for 문 -> 시간복잡도 O(n)
        for ((index, num) in nums.withIndex()) {
        	// HashMap 탐색 -> O(1)
            map[target - num]?.let {
                return intArrayOf(it, index)
            }
            map[num] = index
        }
        return intArrayOf(2)
    }
}

// 시간복잡도 O(n) + O(1) = O(n)

이번엔 중간 분포도에 들어가는 시간복잡도와 공간복잡도가 나왔다!

 

이번에 배운 점

HashMap 의 contains() 가 List 보다 빠른이유

List 는 자료를 저장할 때 순차적으로 저장하기 때문에, 검색 할 때에도 순차적으로 하는 선형 검색을 하기 때문에 O(n)

HashMap 은 값을 저장할 때, HashCode 라는 index 값을 저장하기 때문에 contains() 의 시간복잡도는 O(1)