코테: two sum 2

Yeongjong Kim·2021년 12월 31일

본 문서는 leetcode(https://leetcode.com/problems/two-sum-ii-input-array-is-sorted)를 기준으로 작성하였습니다.

two sum2

문제

정렬된 비 오름차순 배열(numbers)와 특정한 숫자(target)이 주어진다. 배열 내의 두 요소를 더해 target과 일치하는 경우가 무조건 한 가지 존재한다. 두 요소의 index를 i와 j라고 한다면, [i+1, j+1]을 반환하는 함수를 작성하시오.

규칙

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.

문제 풀이 아이디어 생각해보기

numbers의 길이가 3* 1000^4로 비교적 작기 때문에, 두 개의 수로 한정되어 있기 때문에 이중 for문으로 i와 j를 찾아나가면 되겠다는 생각했다.

풀이

유효 아이디 검증 함수는 정규표현식을 이용하기로 했다. 정규표현식중 test라는 메서드를 사용하면 string이 정규표현식과 매칭되는지 확인 후 boolean 형태로 값을 반환한다.

코드

var twoSum = function(numbers, target) {
    for (let i = 0; i < numbers.length; i++) {
        for (let j = i + 1; j < numbers.length; j++) {
            const sum = numbers[i] + numbers[j];
            
            if (sum === target) {
                return [i + 1, j + 1]
            } else if (sum > target) {
                break;
            }
        }
    }
};

문제점

위 코드는, i와 j가 numbers의 맨 마지막에 위치한다면 완벽하게 O(n^2)에 해당하는 시간복잡도를 보여준다. 즉, 배열의 크기가 커질수록 비효율적이다.

다른 사람의 접근법

다른 사람의 풀이를 보면 배열의 양 끝을 포인터로 잡고, 두 요소의 합이 target과 비교하여 큰 경우 혹은 작은 경우에 따라 포인터를 움직이는 방법을 사용했다. 마치 투포인터 알고리즘이 연상된다.

이 알고리즘의 경우 i(left)는 0에서 오른쪽으로 j(right)는 lenfth - 1에서 왼쪽으로 움직이고 두 포인터가 만나는 순간까지 동작하게 된다. 즉 O(n)으로 문제를 해결할 수 있다.

수정 후 최종 코드

var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        
        if (sum === target) 
            return [left + 1, right + 1];
        if (sum < target) {
            left++;
        }
        if (sum > target) {
            right--;
        }    
    }
};