[Java] 167. Two Sum II - Input Array Is Sorted

문제 파악

 

비 내림차순으로 정렬되어 있는 정수 배열 numbers 가 주어진다.

 

배열에서 target 값을 만들 수 있는 값 2개를 찾아, 해당 값의 인덱스를 반환해야한다. ( index1 < index2 )

 

---

 

풀이

 

1️⃣ 투 포인터 방식

💡 떠오른 Idea

인덱스 0 부터 시작하는 left 와 배열의 끝에서 시작하는 right 포인터를 정의한 뒤,

두 값의 합이 target 보다 크면 right 포인터를 감소시키고 target보다 작으면 left 를 증가시키는 방식으로 구현하면 될 것이라 판단했다.

왜냐하면, 비 내림차순으로 정렬되어 있고 정답이 무조건 존재하는 배열로 주어지기 때문에 가능하다고 판단했다.

그리고 시간복잡도도 O(N) 으로 해결할 수 있기 때문이다.

 

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

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

 

Medium 문제 치고 간단하게 해결할 수 있었다.

 

결과

 

 

 

 

2️⃣ 이분탐색 풀이

💡 떠오른 Idea

배열을 순회하면서 하나의 값을 고정으로 두고, 그 이후의 값들 중에서 더했을 때 target 이 되는 값을 이분탐색으로 찾으면 될 것 같다는 생각이 들었다.

배열의 길이도 최대 30000 이기 때문에, 시간 복잡도 O(NlogN) 으로 충분히 통과할 수 있을 것이라 생각이 들었기 때문이다.

 

 

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] ans = null;
        for (int i = 0; i < numbers.length; i++) {
            int fixed = numbers[i];
            int find = target - fixed;

            int result = bs(numbers, i + 1, find);
            if (result != -1) {
                ans = new int[]{i + 1, result + 1};
            }

        }
        return ans;

    }

    private int bs(int[] numbers, int start, int target) {
        int left = start, right = numbers.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target < numbers[mid]) {
                right = mid - 1;
            } else if (target == numbers[mid]) {
                return mid;
            } else {
                left = mid + 1;
            }
        }

        return -1;

    }
}

 

 

 

i 번째 원소를 기준으로, 더했을 때 target 이 되는 수를 i+1 번째 부터 이분 탐색하는 방식이다.

 

결과

 

시간복잡도는 예상한대로 통과할 수 있었다.

 

---

📖 회고

 

이분 탐색 풀이를 도전해서 구현해봤는데, 통과되어서 뿌듯했다.

 

또한, 다른 유형 접근법을 활용함으로서 응용력이 올라간 기분이었다.

 

하나의 문제를 다양한 접근법으로 시도하는 노력을 앞으로도 해봐야겠다는 생각이 들었다.