LeetCode 167(Two Sum II - Input Array Is Sorted, java

0. 문제

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

 

 

1. 문제 설명

- 문제에서 오름차순으로 정렬된 정수형 배열(numbers)과 찾는 수(target)가 주어진다.

- 배열을 탐색하여 두 요소의 합이 target을 이루는 짝을 찾고, 두 요소가 몇 번째 숫자인지 배열에 담아 반환한다.

- 다만, 반환되는 index 또한 오름차순으로 정렬되어야 하며 숫자의 index가 아니라 순번을 반환한다는 것이 핵심이다.

- 여기서 숫자의 순번이란, 0번 index의 요소는 첫 번째 숫자이므로 1을 반환해야 한다.  

 

 

2. 문제 해설

a) 첫 번째 접근

- 문제에서 주어진 몇 가지 힌트가 있는데, 이들을 사용하여 접근하는 것이 중요하다.

- 우선 정답을 담는 배열 또한 오름차순으로 정렬되어야 한다. 

- 단순히 Arrays 라이브러리를 사용하여 정렬할 수도 있으나, 이는 시간 복잡도 측면에서 효율적이지 않다.

- 그러므로 배열을 탐색하는 과정에서 두 요소의 순서를 보장할 수 있어야 한다. 

- 이를 위해서 two pointers 방법을 사용한다.

 

 

b) 두 번째 접근

- 첫 번째 요소를 가리키는 left, 마지막 요소를 가리키는 right를 생성한다.

- while 반복문을 통해 left < right일 때까지 탐색을 수행한다.

 

- 만약 (target - numbers[left])가 numbers[right] 와 동일하다면 반복문을 탈출한다.

- 만약 (target - numbers[left])가 numbers[right] 보다 큰 숫자라면 left를 1 증가시킨다.

- 만약 (target - numbers[left])가 numbers[right] 보다 작은 숫자라면 right를 1 감소시킨다.

 

- 이처럼 left를 증가시키고 right를 감소시키는 이유는 numbers가 오름차순으로 정렬되어 있기 때문이다.

- (target - numbers[left])가 numbers[right] 보다 큰 숫자라면, 이는 더 큰 숫자가 필요한 것이므로 left를 증가시킨다.

- left를 증가시키는 이유는 right는 가장 큰 숫자(= 마지막 요소)부터 시작했으므로 감소만 가능하기 때문이다.

- 반대의 상황에서는 right를 감소시킨다. 그 이유 또한 left를 증가시키는 이유와 동일한 원리로 적용된다.

 

- 다음 코드를 보면서 이해해보자.

 

  

3. 정답 코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        
        int left = 0;
        int right = numbers.length - 1;
        
        while(left < right) {
            int findNum = target - numbers[left];
            
            if(numbers[right] == findNum) break;
            else if(numbers[right] > findNum) right--;
            else if(numbers[right] < findNum) left++;
        }
        return new int[]{left + 1, right + 1};
    }
}