[백준] 3273 두 수의 합

Posted on | In

투포인터 문제는 예전에도 그랬지만 감이 안 잡힌다. :O 그래서 공부를 하고 문제를 풀려고 하는데두 예시 문제 설명이구 내가 막 와닿게 이해되지는 않는 거 같다 .

문제 설명

리스트를 입력 받아서 두 수의 합이 특정값 x인 쌍들이 몇개인지 출력하는 문제이다. 단순히 이중 포문 써서 모든 경우를 흝으면서 세면 되겠지만, 이렇게 되면 시간복잡도가 O(n^2)이 되서 시간 초과가 뜨게 된다. 따라서 투포인터를 사용해서 문제를 풀어야 한다.

문제 풀이

나는 이분 풀이를 참고했다. 감사합니다ㅠㅠ

나는 리스트가 sort되어 있다면 체크하지 않아 알 수 있는 경우가 많아질 것 같아서 sort를 진행했다. 그 이후, 투포인터 문제이므로 s와 e를 정해주어야 한다. 좀 생각해야 하는 부분은 s은 리스트의 시작점, e은 리스트의 끝점을 가리킨다는 점이다. 나는 e도 리스트의 시작점을 가리키는 줄 알고 계속 헤맸는데 e가 리스트의 끝을 가리키면 문제가 좀 편해진다. 만약 s가 e를 넘어가면 더 이상 고려하지 않아도 되게 된다. 따라서 while(true)의 break는 s>=e일때 걸린다. 그리고 a[s]+a[e]가 딱 x가 되는 경우가 뜻하는 걸 잘 알아야 한다. a 리스트 안의 값들이 모두 다른 수 이므로, 연속되서 두 합이 x인 경우는 없다. 그리고 생각해보면, s가 커지면 a[s]+a[e] 값이 커지고, e가 커지면 a[s]+a[e] 값이 작아진다. 따라서 a[s]+a[e]가 x보다 작으면 s를 키우고, a[s]+a[e]가 x보다 크면 e를 줄이면서 x에 맞춰가면 된다. 그래서 a[s]+a[e]가 딱 x가 되는 경우에는, s를 키워주고 e를 줄여줌으로써 그 다음 경우를 고려할 수 있다.

코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int n,x;
    int a[100001];

    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", &a[i]);
    sort(a, a+n);
    scanf("%d", &x);

    int s=0,e=n-1;
    int ans=0;

    while(true){
        if(s>=e) break;
        int sum = a[s]+a[e];

        if(sum==x) {
            ans++;
            s++;
            e--;
        }

        else if(sum<x) s++;
        else e--;
    }
    printf("%d\n", ans);
}