[ Top Interview 150 ] 167. Two Sum II - Input Array Is Sorted

문제

167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is
exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

• Input : 오름차순으로 정렬되어 있는 1차원 int 배열 numbers, 특정 두 숫자의 합 target
• Output : 1차원 배열에서 특정 두 숫자의 위치 [index1, index2] (index1 < index2)
• Condition
  • 조건을 만족하는 [index1, index2]는 반드시 단 한가지이다.
  • 같은 숫자를 두 번 이용할 수 없다.
  • Space complexity O(1)을 만족해라.

알고리즘 전략

• 문제 조건 분석

  • numbers라는 선형 데이터 제공
  • 합이 target이 되는 2개의 쌍을 찾는 문제
  • 두 숫자의 위치가 어디 있을지 모르므로 두 포인터를 동시에 움직여야 함
  • 따라서 Two Pointer Algorithm을 이용하여 문제를 품

• 해결 전략

  • 초기 두 숫자 위치를 front, behind로 설정
    • 기본 값은 각각 numbers의 맨 앞과 맨 뒤로 한다.
  • 두 숫자의 합을 sum이라고 할 때
    • sum이 target보다 크다면, behind를 이전 값으로 한다.
    • sum이 target보다 작다면, front를 다음 값으로 한다.
    • sum이 target보다 같다면, [front, behind]를 반환한다.

1차 작성

• Time complexity : O(n)
• Space complexity: O(1)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int front = 0;
        int behind = numbers.length - 1;

        while (front < behind) {
            int sum = numbers[front] + numbers[behind];
            if (sum > target) {
                behind--;
            } else if (sum < target) {
                front++;
            } else {
                return new int[]{front + 1, behind + 1};
            }
        }

        return new int[0];
    }
}

모범 답안

• 기본적인 전략은 위와 동일하다.
• 분기점 하나를 생략하여 성능을 개선하였다.
  • 아래 답안에는 numbers가 딱 하나의 답안을 가진다는 전제를 두기 때문에 해당 분이를 없애 조건문을 조금 덜 사용하도록 했다.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int front = 0;
        int behind = numbers.length - 1;

        int sum = numbers[front] + numbers[behind];
        while (sum != target) {
            if (sum > target) {
                behind--;
            } else {
                front++;
            }
            sum = numbers[front] + numbers[behind];
        }

        return new int[]{front + 1, behind + 1};
    }
}

답안 비교

• 위 1차 작성한 답안에서는 혹여나 정답이 없는 경우에는 []이 반환되는 분기점이 포함되어 있다.
• 모범 답안에는 해당 분기문이 포함되어 있지 않다.
  • 만약 정답이 없는 경우 계속적으로 반복하다가 OutOfIndex에러를 내어 프로그램이 중단될 수 있다.
• 실제 비즈니스에서는 특정 조건임을 보장할 수 없기 때문에 위 방법이 조금 더 나아보인다. (정확하게는 오른차순임도 확인해야 겠지만)