leetcode easy - Two Sum

문제

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.

Integer 타입의 배열이 있고, 이중 2개를 뽑아 더해서 target과 같은 값이 나오는 인덱스를 반환해야 한다.

예제 1

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

예제 2

Input: nums = [3,2,4], target = 6 Output: [1,2]

예제 3

Input: nums = [3,3], target = 6 Output: [0,1]

제약 사항

• 2 <= nums.length <= 10000
• -10,000,000,000 <= nums[i] <= 10,000,000,000
• -10,000,000,000 <= target <= 10,000,000,000

해결

쉽게 접근해서 반복문 2번이면 끝난다. 그런데 시간복잡도가 O(n제곱)보다 작아야 한다.

일단 성능적 요구사항까진 생각하지말고. 기능적 요구사항이라도 맞게끔 해보자.

public static int[] twoSum1(int[] nums, int target) {
    int[] result = new int[2];
    for (int i = 0; i < nums.length-1; i++) {
        for (int j = i+1; j < nums.length; j++) {
            if (nums[i]+nums[j] == target) {
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return result;
}

반복문 두 번 돌리면서 더한값이 target과 일치하면 result 배열에 인덱스를 저장하고 반복문을 나온다.

n제곱의 시간복잡도를 상수까진 못해도 n으로는 줄일 수 있을 것 같다.

이럴 때 바로 생각해볼 수 있는 접근은 중첩된 for문을 풀어서 쓰는 것이다. n * n을 n + n정도로 바꾼다는 말이다.

target은 상수(메서드 변수로 들어오지만 아무튼 코드 블럭 내에서는 변하지 않는다)로 정해져있다. 첫번째 반복문에서 이 상수를 가지고 뭔가를 연산한 다음에 두번째 반복문에서 이 연산값을 활용하면 좋을 것 같다.

num[i] + num[j] = target 공식에서 target을 좌변으로 빼보자.

num[i] - target = -num[j]가 된다. 마이너스는 보기 싫으니까 target - num[i] = num[j]로 바꿔 쓸 수 있다.

코드가 나올 것 같다. 좌변에서 연산한 값을 첫번째 반복문에서 어딘가에 저장해두고, 우변에 있는 값과 비교한다.

우변은 인덱스를 반복문을 돌면서 알 수 있고, 좌변은 인덱스를 어딘가에 저장해야 되니 key-value 자료구조인 Map을 활용하면 될 것 같다. 그럼 두번째 반복문에서 Map에 key로 바로 접근하면 target - num[i] = num[j] 공식이 코드로 구현되는 것이다.

아래는 이 사고과정을 거쳐 나온 코드이다.

public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];

    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }

    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (map.containsKey(diff) && map.get(diff) != i) {
            result[0] = map.get(diff);
            result[1] = i;
            break;
        }
    }

    return result;
}

첫번째 코드에서 Runtime이 67ms 걸렸었는데, 두번째 코드에서는 4ms로 대폭 개선되었다.

베스트 프랙티스에서는 첫번째, 두번째 반복문 합쳐서 바로 비교하고 리턴하는 형태였는데, 역시 뭔가 개선점은 더 있었다.

 

오랜만에 코딩 테스트 연습하려니 뇌에 마사지가 필요한 것 같다.