[공부] 백준 3273 두 수의 합(투포인터 문제)

📝 문제

• 백준 3273 집합
  • https://www.acmicpc.net/problem/3273

---

🔍 문제 상황

예제 입력 1

---

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1

3

---

💡 해결 방법 / 접근 방식

• 투 포인터를 활용하여 접근해야함

투 포인터란(Two Pointers)?

• 출처: https://velog.io/@tmdwns1521/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-Two-Pointers
• 이름 그대로 포인터를 2개 써서 배열에 순차적으로 접근(순회)하는데, 특정 조건을 만족하는 값을 빠르게 찾는 알고리즘을 말합니다.
• 이때 포인터는 실제 C/C++의 포인터 개념(우리가 아는 포인터(int* iPtr;))과는 다르고, 배열의 “위치”를 가리키는 두 변수를 의미합니다.
• 보통 한 포인터는 배열의 시작부터, 다른 포인터는 끝에서부터 시작하며, 두 포인터의 이동 규칙을 잘 정의하면 완전 탐색(O(N^2))보다 효율적으로 동작(O(NlogN) 또는 O(N))합니다.

접근 방식

• 우선 정렬을 안해주어도 문제없지만, 정렬해주면 편하기에 오름차순으로 정렬해줍니다.
• 그 후에 left(왼쪽 포인터)는 시작점(0)으로, right(오른쪽 포인터)는 끝점(n-1)에서 시작합니다.
• 두 숫자의 합(sum = v[left] + v[right])이 x와 같은지 비교하는데 이때
  • 합이 x보다 작으면, left(왼쪽 포인터) 값이 작으므로 left(왼쪽 포인터)를 증감시킵니다.
  • 합이 x보다 크면, right(오른쪽 포인터) 값이 크므로 right(오른쪽 포인터) 감소시킵니다.
  • 합이 x와 같으면, 쌍이므로 cnt를 증가하고, right(오른쪽 포인터)를 감소 시킵니다.

• 두 포인터가 교차하면 종료됩니다.

🛠️ 구현 코드

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

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, x;
    cin >> n;
    // 수열을 벡터로 입력 받기
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    cin >> x;

    // 정렬 안해줘도 되지만 하면 좋음
    sort(v.begin(), v.end());

    // 왼쪽 포인터, 오른쪽 포인터 선언
    int left = 0, right = n - 1;
    // 카운터 선언
    int cnt = 0;
    // 포인터의 위치(값이)가 최종적으로 서로 만났을(같아졌을) 때 최종 종료됨
    // 이걸 쓰는 이유가 완탐시 시간 복잡도를 줄일 수 있음
    while (left < right) {
        int sum = v[left] + v[right];
        if (sum == x) {
            // 카운트 증가 및 오른쪽 포인터 감소
            cnt++;
            right--;
        } else if (sum > x) {
            // 오른쪽 포인터 값이 크므로 감소시키기
            right--;
        } else {
            // 왼쪽 포인터 값이 작으므로 증감시키기
            left++;
        }
    }
    cout << cnt;
    return 0;
}

🧷 결론

• 이번 문제는 투 포인터에 대한 개념과 구조를 파악하기에 용이한 문제라고 판단됩니다.
• 그래서 투 포인터를 이해하고자 한다면 반드시 풀어보면 좋은 문제이며, 이를 응용해서 투 포인터 유형의 문제를 풀어보면 좋을 것 같습니다.