[LeetCode/easy] TwoSum

 

 

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

두 개의 원소 합이 target인 원소의 인덱스를 출력하는 문제

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> nums = {3,2,4}; // 2 3 4
    int target = 6;
    int l = 0, r = nums.size()-1;
    vector<pair<int, int>> tmp;

    for(int i=0; i<nums.size(); i++) tmp.push_back({i, nums[i]});

    vector<int> answer;
    sort(tmp.begin(), tmp.end(), compare);

    while(r > l && tmp[r].second + tmp[l].second != target){
        if(tmp[l].second + tmp[r].second > target) r--;
        else                                       l++;
    }

    if(tmp[r].second + tmp[l].second == target){
        answer.push_back(tmp[l].first);
        answer.push_back(tmp[r].first);
    }
}

 

배열을 정렬해서 앞 뒤 포인터를 중앙으로 이동하면서 합을 target과 비교하며 돌리다 보면 나온다. 두 개의 포인터가 하나의 원소를 가리키면 안 되므로(+ 엇갈려서 l>r 이 되면 안 됨) 조건을 추가해준다 (while(r> l))

• 두 원소의 합이 target보다 크다면 오른쪽 원소를 가리키는 포인터를 앞으로 이동(r--) 
• 두 원소의 합이 target보다 작다면 왼쪽 원소를 가리키는 포인터를 뒤로 이동(l++)

이때, 원래 배열을 정렬을 하면 출력해야 하는 초기 배열 인덱스 값이 올바르게 출력할 수 없다.

그러므로 vector<pair<int, int>>를 사용해서 정렬 전의 배열 인덱스와 값을 넣어준다. (first: index, second: value)