[백준(BOJ)] 3273번: 두 수의 합 (Two Pointers Algorithm, C++)

 

💻 C++  제출코드

---

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N, X; 
    
    int count=0;

    scanf("%d", &N);
    int right=N-1, left=0;
    vector<int> A(N);

    for(int i=0; i<N; i++){
        cin >> A[i];
    }

    scanf("%d", &X);
    
    sort(A.begin(), A.end());

    while(1){
        if(left >= right) break;
        int sum = A[left]+A[right];
        if(sum == X){ 
            count++;
            left++; 
        }
        if(sum >= X) right--;
        if(sum < X) left++;
        
    }
    
    printf("%d", count);

}

 

 

 

 

📝 문제풀이 과정

---

1. 정렬

• sort로 정렬

 

2. left = 0, right = N-1에서 탐색 시작

• sum은 반복문 내에서 선언해서 사용 -> 밖에서 sum을 선언하고 반복문 내에서 사용하면 제대로 결과가 나오지 않는다.

 

3. sum = A[left] + A[right]일 때

• sum == X: count 증가시키고 다음 탐색 위해 left++, right--

• sum > X: 수가 더 작아져야 하므로 right을 감소시킨다.

• sum < X: 수가 더 커져야 하므로 left를 증가시킨다.

 

4. 반복조건

•  left는 계속 증가하고, right은 계속 감소하므로 left >= right일 때 종료한다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main()
{
    int N, X; //N: 양의 정수 개수, X: 타겟 합
    
    unordered_map<int, int> m;

    scanf("%d", &N);
    int right=N-1, left=0;
    vector<int> A(N);

    for(int i=0; i<N; i++){
        cin >> A[i];
    }

    scanf("%d", &X);
    
    sort(A.begin(), A.end());
    
    while(1){
        if(left >= right) break;
        printf("left: %d, right: %d\n", left, right);
        int sum = A[left]+A[right];
        if(sum == X){ 
            printf("(%d, %d)\n", A[left], A[right]);
            m.insert({A[left], A[right]});
            left++; 
        }
        if(sum >= X) right--;
        if(sum < X) left++;
        
    }
    
    for(auto i: m)
        printf("(%d, %d) ", i.first, i.second);
    printf("\n# of X: %d", m.size());

}

• 마지막에 A[3], A[5]일 때 타겟 합 X보다 커서 right을 감소시켰는데 A[3]+A[4]일 때는 더 작아서 left를 증가시켰을 것이다.

• 따라서 위의 케이스의 경우, left == right이 되므로 반복문에서 빠져나오게 된다.

• 위 코드는 제대로 구하는지 검증하기 위한 코드이다.

 

 

 

👏 결과

---