🟠[Leet code - 167] Two Sum II - Input Array Is Sorted ✅

Two Sum II - Input Array Is Sorted - LeetCode

문제

• Input
  오름차순으로 정렬된 정수 배열 numbers
  정수 target
• Output
  numbers 원소중 두 개를 더하여 target이 되는 두 인덱스
  (인덱스는 zero-based가 아닌 1부터 시작하는 one-based로 반환한다.)
• Constraints
  numbers는 오름차순으로 정렬되어 있다.
  동일한 요소 두 번 사용 불가능
  오직 하나의 답 존재
  상수 공간 복잡도로 풀이해야 한다.

 

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관없음 | O(log n) : 크게  상관없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

$2 \le n \le 30'000$ 으로 $O(n \log n)$부터 고려해 볼 수 있다.

 

해결 과정

바로 떠오른 계획은,

$a + b = \text{target}$이므로 a를 저장해 가며 $target - a$가 등장했었는지에 대해

map에 저장하여 확인하는 풀이방법이 생각났지만, 상수 공간 복잡도가 아니므로 다른 방법을 찾았다.

 

두 번째 계획으로는,

target - number [i]를 이분 탐색하여 존재하는지 찾는 방법이었다.

복잡도면에서 모두 통과 가능한 방법 같았지만, 뭔가 문제에서 의도하는 정답은 아닌 것 같아서 일단 보류했다.

 

그래서 좀 더 고민해 봤는데, 상수 공간 복잡도로 풀이하라는 뜻이 순회하다가 정답을 찾는 느낌으로 다가왔다.

이는 즉, 순회하는 동시에 정답 확인이 가능해야 한다는 느낌과 같다.

 

문제는 어떻게 정답 확인을 하느냐였는데, 뭔가 정렬되어 있다는 게 힌트 같았다.

굳이 정렬을 해놓았다고 한 거 보니까 "정렬되어 있으니까 이론상 이런 방법이 가능함!" 이런 느낌이어서 정렬을 해야만 가능한 방법이 뭐가 있을까 고민했다.

 

그러다가 문득 생각난 게 있는데, 만약 두 인덱스 left와 right가 있다고 가정할 때, left와 right의 합이 target이 아니라면 right의 오른쪽에 존재하는 원소는 확인하지 않아도 답이 아니지 않나?라는 아이디어에서 답을 점점 구체화시켰다.

 

맨 앞과 맨 뒤에서 두 가지 인덱스를 이용하여 순회한다.
포인터의 합이 target보다 크면 뒤의 포인터를 줄이고,
포인터의 합이 target보다 작으면 앞의 포인터를 증가하면 된다.

이 방법은 오름차순 정렬로 되어 있기 때문에 가능한 방법이고, O(n)으로 통과 가능하기 때문에

문제의 의도와 굉장히 적합하다고 생각하여 해당 방법으로 바로 진행했다.

아래와 같은 수도 코드를 작성했었다.

WHILE(l < r)
{
    int sum = num[l] + num[r];

    IF (sum == target) return l AND r
    IF (sum < target) ++l;
    IF (target < sum) --r;
}

 

 

구현

vector<int> twoSum(vector<int>& numbers, int target) 
{
    auto& num = numbers;

    int l = 0;
    int r = num.size() - 1;
    
    while (l < r)
    {
        int sum = num[l] + num[r];

        if (sum == target) return {l + 1, r + 1};
        sum < target ? ++l : --r;
    }

    // 답이 존재하지 않을 때 반환하는 부분 = 문제 조건상 도달하지 않는 부분
    return {};
}

 

 

되돌아보기

정렬된 배열이라는 조건

돌아보니까 정렬되었다는 뜻이 굉장히 강한 힌트였다.

다음에도 정렬이 되어있다는 힌트가 있다면, 정렬되었기 때문에 이번 문제의 투 포인터처럼

중복 탐색을 피할 수 있는 방법을 생각해 봐야겠다!