Two Sum II - Input Array Is Sorted

💬 문제

[문제 링크]

오름차순으로 정렬된 정수 배열 numbers
두 요소의 합이 정수 target이 되는 인덱스 위치(인덱스 번호 + 1) 배열로 반환
무조건 하나의 정답만 있음

✍️ 나의 풀이

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        let sum = numbers[left] + numbers[right];
        if (sum === target)
            return [left + 1, right + 1];
        if (sum > target)
            right--;
        else
            left++;
    }

    return [left + 1, right + 1];
};

배열의 왼쪽 끝과 오른쪽 끝 값을 더해보면서
같으면 인덱스 + 1한 값을 배열로 반환
다르면 둘 더한 값과 target 비교
오름차순 정렬이기 때문에 더한 값이 크다면 오른쪽 인덱스 감소
target보다 작다면 왼쪽 인덱스 증가

📌 결과

Accepted
Runtime 57ms (Beats 51.48%)
Memory 50.06MB (Beats 43.43%)

📚 러닝 포인트

오늘은 뇌에 힘이 안들어가는 날이어서 그런지 분명 처음에 왼쪽 끝과 오른쪽 끝에서 점점 줄여가면서 답을 찾아야겠다, 생각했는데 왼쪽과 오른쪽 중에 어떤걸 먼저 증감시켜야 될지 머리가 잘 안돌아갔다. 그래서 그냥 단순하게 for문 중첩으로 돌렸더니 역시나 실행시간이 너무 길어서 실패했다. 그러던 중 오름차순 정렬이라는 것을 이용해서 더했을 때 target보다 작으면 왼쪽을 증가하고, 크면 오른쪽을 증가함으로써 값을 맞춰나갈 수 있다는 것을 알아냈다. 참 단순했던 알고리즘이라 이걸 바로 생각해내지 못했던게 조금 분하긴 하다. 다음부터는 정신 똑바로 차리고 구상해야지.