Silver III 난이도 문제를 C++로 풀이한 내용입니다. 주어진 배열에서 합이 특정 값 `x`가 되는 두 수의 쌍의 개수를 찾는 문제입니다.

백준 3273: 두 수의 합

Silver III 난이도 문제를 C++로 풀이한 내용입니다. 주어진 배열에서 합이 특정 값 x가 되는 두 수의 쌍의 개수를 찾는 문제입니다.

문제 소개

문제 번호: 3273
문제명: 두 수의 합
난이도 (티어): Silver III
사용 언어: C++
실행 시간: 8 ms
메모리: 2412 KB
문제 요약: N개의 서로 다른 양의 정수로 이루어진 배열이 주어지고, 합이 x가 되는 두 수의 쌍의 개수를 구해야 합니다.

접근 방법

문제를 처음 접했을 때, 가장 직관적인 방법은 배열의 모든 가능한 두 수의 쌍을 탐색하여 합을 비교하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(N^2)이 되어 N이 클 경우 시간 초과가 발생할 수 있습니다.

N개의 원소에서 합이 x가 되는 두 수를 찾는 문제에서, 배열을 정렬하면 투 포인터(Two Pointers) 기법을 효과적으로 사용할 수 있습니다. 배열을 오름차순으로 정렬한 후, 배열의 양 끝에서 시작하는 두 개의 포인터(left, right)를 사용하여 합을 계산하고, 이 합을 목표값 x와 비교하며 포인터를 이동시키는 방식입니다.

사용 알고리즘/자료구조: 정렬(Sorting), 투 포인터(Two Pointers)
선택 이유:
- 정렬을 통해 데이터에 순서를 부여하여 효율적인 탐색이 가능합니다.
- 투 포인터 기법은 정렬된 배열에서 특정 조건을 만족하는 쌍을 찾는 데 O(N)의 시간 복잡도를 가지므로, 전체 시간 복잡도를 O(N log N) (정렬 시간) + O(N) (투 포인터) = O(N log N)으로 줄일 수 있습니다. 이는 O(N^2)보다 훨씬 효율적입니다.

풀이 과정

입력 받기: 배열의 크기 n과 목표 합 x를 입력받습니다.
배열 저장: n개의 정수를 std::vector에 저장합니다.
배열 정렬: std::sort 함수를 사용하여 벡터 v를 오름차순으로 정렬합니다.
투 포인터 초기화: 왼쪽 포인터 left를 0으로, 오른쪽 포인터 right를 n-1로 초기화합니다. 합을 셀 count 변수는 0으로 초기화합니다.
투 포인터 탐색: left가 right보다 작은 동안 다음을 반복합니다.
- 현재 left와 right 포인터가 가리키는 두 수의 합 sum = v[left] + v[right]을 계산합니다.
- sum == x인 경우: 두 수의 합이 x와 같습니다. 이 쌍은 조건을 만족하므로 count를 1 증가시킵니다. 이후 left와 right 포인터를 각각 1씩 증가 및 감소시켜 다른 쌍을 탐색합니다. (이미 검사한 쌍을 다시 검사하거나, x를 만들 수 없는 방향으로 이동하는 것을 방지하기 위해 둘 다 이동합니다.)
- sum < x인 경우: 두 수의 합이 x보다 작습니다. 합을 증가시키기 위해 더 큰 값을 가진 v[left]를 사용해야 하므로 left 포인터를 1 증가시킵니다.
- sum > x인 경우: 두 수의 합이 x보다 큽니다. 합을 감소시키기 위해 더 작은 값을 가진 v[right]를 사용해야 하므로 right 포인터를 1 감소시킵니다.
결과 출력: 반복이 끝나면 count에 저장된 두 수의 합이 x가 되는 쌍의 개수를 출력합니다.

핵심 아이디어: 정렬된 배열에서 양 끝의 두 수를 더하고, 그 합과 목표값 x를 비교하여 포인터를 효율적으로 이동시키며 탐색합니다.
주의할 점:
- 입력되는 수들이 서로 다른 양수라는 조건이 중요합니다. 이로 인해 sum == x일 때 left와 right를 모두 이동시키더라도 중복된 쌍을 세지 않게 됩니다.
- left < right 조건을 유지하여 자기 자신과의 합을 고려하지 않도록 합니다.

코드 설명

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

int main() {
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, x; // n: 배열의 크기, x: 목표 합
    cin >> n;
    
    vector<int> v(n); // n개의 정수를 저장할 벡터
    // 벡터에 n개의 정수 입력
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    cin >> x; // 목표 합 x 입력
    
    // 벡터 v를 오름차순으로 정렬
    sort(v.begin(), v.end());
    
    int left = 0; // 왼쪽 포인터 초기화
    int right = n - 1; // 오른쪽 포인터 초기화
    int count = 0; // 조건을 만족하는 쌍의 개수를 저장할 변수 초기화
    
    // left 포인터가 right 포인터보다 작은 동안 반복
    while (left < right) {
        int sum = v[left] + v[right]; // 현재 left와 right가 가리키는 두 수의 합 계산
        
        if (sum == x) {
            // 합이 x와 같은 경우, 조건을 만족하는 쌍을 찾았으므로 count 증가
            // L만 또는 R만 움직이면 다시 x가 될 수 없음(입력들이 서로 다른 양수였기 때문에 중복이 없으므로)
            // 그러므로 둘 중 하나만 이동하는 건 배제
            // L++, R--로 둘 다 이동
            // (L--, R++로 돌아가면 이미 검사한 조합을 다시 검사하게 되므로 금지)
            count++;
            left++; // 왼쪽 포인터 오른쪽으로 이동
            right--; // 오른쪽 포인터 왼쪽으로 이동
        } else if (sum < x) {
            // 합이 x보다 작은 경우, 합을 증가시키기 위해 left 포인터 이동
            // R++은 과거에 이미 시도되었거나 배제된 쌍이므로
            left++;
        } else { // sum > x
            // 합이 x보다 큰 경우, 합을 감소시키기 위해 right 포인터 이동
            // L--은 과거에 이미 시도되었거나 배제된 쌍이므로
            right--;
        }
    }
    
    // 조건을 만족하는 쌍의 개수 출력
    cout << count << endl;
    
    return 0;
}

복잡도 분석

시간 복잡도: O(N log N)
- 배열을 정렬하는 데 O(N log N) 시간이 소요됩니다.
- 투 포인터 탐색은 left와 right 포인터가 각각 한 번씩만 이동하며 배열을 순회하므로 O(N) 시간이 소요됩니다.
- 따라서 전체 시간 복잡도는 O(N log N + N) = O(N log N)입니다.
공간 복잡도: O(N)
- 입력 배열 v를 저장하기 위해 O(N)의 공간이 필요합니다.
- 추가적인 변수들은 상수 공간 O(1)을 차지합니다.

배운 점

이 문제를 통해 정렬된 배열에서 효율적으로 쌍을 찾는 투 포인터 기법의 유용성을 다시 한번 확인할 수 있었습니다. 또한, 문제의 제약 조건(서로 다른 양수)이 알고리즘 선택 및 구현에 미치는 영향을 이해하는 것이 중요함을 깨달았습니다. O(N^2)의 무차별 대입 방식으로는 해결하기 어려운 문제들을 O(N log N) 또는 O(N)의 알고리즘으로 최적화하는 연습이 필요합니다.