[C++] [CSES] Sum of Two Values (Sorting and Searching)

CSES Sorting and Searching 일곱번째 문제입니다.

leetcode의 Two Sum 문제와 같습니다. 각종 블로그와 플랫폼에 이 문제를 최적화해가는 과정이 많이 있습니다.

저는 map을 이용한 방법으로 풀었습니다.

 

Task

 

You are given an array of n integers, and your task is to find two values (at distinct positions) whose sum is x.

Input

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a1,a2,…,an: the array values.

Output

Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints

• 1≤n≤2⋅1e5
• 1≤x,ai≤1e9

Example

Input:
4 8
2 7 5 1

Output:
2 4

 

Code

#include<bits/stdc++.h>
using namespace std;

int n, x, num;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> x;
    vector<int> ar(n);
    map<int, int> mp;
    for (int i=1;i<=n;i++) {
        cin >> num;
        if (mp.find(num) != mp.end()){
            auto it = mp.find(num);
            cout << it->second << " " << i;
            return 0;
        }
        mp.insert({x - num, i});
    }
    cout << "IMPOSSIBLE";
}

생각해야 하는 것

• map에는 x - num을 key, 인덱스를 value로 저장했습니다.
• 숫자를 받았을 때 map 안에서 받은 숫자의 key가 있는지 확인합니다.
• 있다면 바로 인덱스들을 출력하고 종료합니다.
• 없다면 {x - num, i}를 저장합니다.
• 모든 숫자를 다 받았지만 리턴이 되지 않은 경우 매칭되는 쌍이 없기 때문에 IMPOSSIBLE을 출력하고 종료합니다.
• pair<숫자, 인덱스> 정렬 후 투포인터 기법을 이용할 수도 있을 것 같습니다. 이때 인덱스의 순서가 뒤바뀔 수 있기 때문에 이때는 min, max로 감싸서 출력하면 될 것 같습니다.