CSES 2. Sum of Two Values (1640)

출처: https://cses.fi/problemset/task/1640

---

문제 설명

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

입력 

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

The second line has n integers a_1,a_2,…,a_n : the array values.

출력 

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.

입력 예

4 8
2 7 5 1

출력 예

2 4

제약조건

• 1 <= n <= 2x10^5
• 1 <= x, a_i <= 10^9

---

문제 풀이 

입력받은 문자열의 값과 위치를 저장하고, 값을 기준으로 정렬한다.

양쪽에서 출발해서 맞는 값을 찾는다.

작은 값(left)과 큰 값(right)을 더해서 원하는 값과 비교해서 작으면 (left++), 값이 더 크면 (right--) 진행한다.  

답이 있는면 위치를 출력하고,  해당하는 값이 없는 경우 IMPOSSIBLE 출력한다.

프로그램 내용

...
    vector <pair <long, long> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        num_arr.push_back({temp, idx});

	sort(num_arr.begin(), num_arr.end()); 

    int idx=0, id = nNum-1;			// double pointer
    while( idx < id )
        int k = num_arr[idx].first + num_arr[id].first;

        if (k == tSum)
            cout << num_arr[idx].second + 1 << " " << num_arr[id].second + 1 << endl;
        else if ( k < tSum ) idx++;
        else id--;

 

Sorting and Searching ( link )