[Leetcode/C++] 167_Two Sum II - Input Array Is Sorted

문제는 다음과 같습니다.

먼저 제 풀이는 다음과 같습니다.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> cnt; // 개수를 저장
        unordered_map<int, int> idx; // 인덱스를 저장
        vector<int> res; // 결과벡터
        
        for(int i=0; i<numbers.size(); i++){
            cnt[numbers[i]]++;
            idx[numbers[i]]=i+1;
        }
        
        for(int i=0; i<numbers.size(); i++){
            if(numbers[i] != target-numbers[i]){
                if(cnt[numbers[i]]>0 && cnt[target-numbers[i]]>0){
                    res.push_back(idx[numbers[i]]);
                    res.push_back(idx[target-numbers[i]]);
                    break;
                }
            }
            else{ // numbers[i] == target - numbers[i] 인 경우
                if(cnt[numbers[i]]>1){ // 개수가 2개인 경우에만 성립
                    res.push_back(idx[numbers[i]]-1);
                    res.push_back(idx[numbers[i]]);
                    // 같은 값이 두번 들어간 경우, 두번째 값의 인덱스 값으로 들어감
                    break;
                }
            }
        } // for문 끝
        sort(res.begin(), res.end());
        return res;
    }
};

먼저, 주의해야 할 부분은 여기인 것 같습니다.
고른 두 수가 다른 경우와 같은 경우로 나누는 것입니다.

• 다른 경우: numbers[i] != target - numbers[i]
• 같은 경우: numbers[i] == target - numbers[i]

다른 경우에는 cnt의 값이 1이기만 해도 만족하지만,
고른 두 수가 같은 경우에는 같은 cnt를 참조해야 하므로 cnt>1이어야 합니다.

또, 같은 경우에 인덱스를 어떻게 찾느냐가 관건인데,
저는 같은 값이 계속되서 갱신되면 이건 어떡하지..?라고 생각했는데 그럴 이유가 없었네요 ㅎㅎ
답은 하나로 정해져있다고 했고, 그러면 값이 같은 경우는 2가지가 최대이고 그 이상으로는 없는 것입니다.
그러면, 만약 같은 두 값이 있다면 idx에는 가장 마지막에 있는값의 인덱스로 갱신이 되었을 것입니다.
그럼 바로 이전은 -1을 하여 구하면 됩니다!

속도도 나쁘지 않게 나온 것 같습니다.

원래는 unordered_map<int, pair<int, int>>를 이용할라고 했는데, 이걸 이용해서도 다시 풀어보겠습니다!

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, pair<int, int>> um; // <개수, 인덱스 저장>
        vector<int> res; // 결과벡터
        
        for(int i=0; i<numbers.size(); i++){
            if(um[numbers[i]].first>0){
                int tmp = um[numbers[i]].first;
                um[numbers[i]]=make_pair(um[numbers[i]].first +1, i+1);
            }
            else{
                um[numbers[i]]=make_pair(1, i+1);
            }
        }
        
        for(int i=0; i<numbers.size(); i++){
            if(numbers[i] != target-numbers[i]){
                if(um[numbers[i]].first > 0 && um[target-numbers[i]].first > 0){
                    res.push_back(um[numbers[i]].second);
                    res.push_back(um[target-numbers[i]].second);
                    break;
                }
            }
            else{ // numbers[i] == target - numbers[i] 인 경우
                if(um[numbers[i]].first > 1){
                    res.push_back(um[numbers[i]].second);
                    res.push_back(um[numbers[i]].second - 1);
                    // 같은 값이 두번 들어간 경우, 두번째 값의 인덱스 값으로 들어감
                    break;
                }
            }
        } // for문 끝
        sort(res.begin(), res.end());
        return res;
    }
};

속도는 거의 같지만 메모리를 더 줄여본 풀이입니다 ㅎㅎ

뭔가 더 쉽게 풀 수도 있을 것 같은데,
다른분들은 어떻게 풀었는지 비교해볼게요!

• 풀이1: Two Pointer technique

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0,j=nums.size()-1;
        while(i<j){
            int sum = nums[i] + nums[j];
            if(sum==target) return {i+1,j+1};
            else if(sum>target) j--;
            else i++;
        }
        return {}; // not found
    }
};

• 시간복잡도: O(n)
• 공간복잡도: O(1)

• 풀이2: Using Binary Search

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        for(int i=0; i<n-1; i++){
            int lo = i+1;
            int hi = n-1;
            while(lo<=hi){
                int mid = (lo+hi)/2;
                if(numbers[mid]==target-numbers[i]) return { i+1, mid+1 };
                else if(numbers[mid]<target-numbers[i]) lo=mid+1;
                else hi=mid-1;
            }
        }
        return {};
    }
};

• 시간복잡도: O(nlogn)
• 공간복잡도: O(1)

참고풀이 출처

네,, 이렇게 간단히도 풀 수 있겠네용😊