[백준 BOJ/C++] 3273 두 수의 합

 

3273번: 두 수의 합

 

기본 개념이나 알고리즘을 연습하기 좋은 실버난이도의 문제다.
투 포인터 (Two Pointer) 알고리즘을 이용하면 간단히 풀 수 있다.

 

서로 다른 양의 정수들로 이루어진 배열에서 두 수를 골라 더해서 특정 값을 만들 수 있는 숫자 쌍을 찾는 문제다.

특별히 꼬아놓거나 이해가 어렵게 설명한 문제는 아니라서 비슷한 유형의 문제를 접해봤었다면 접근이 어렵지 않다.

 

 

크게 두가지 과정을 거치면 되는데 바로 정렬과 투 포인터 알고리즘 (Two Pointer Algorithm)이다.

 

 

---

 

 

문제의 포인트

 

Two Pointer Algorithm

 

투 포인터 알고리즘을 모르고 있더라도 문제를 보면 아이디어를 찾기 어려운 편은 아니다.

먼저 배열의 탐색을 쉽게 할 수 있도록 정렬이 필요함을 생각해 볼 수 있다.

직접 대소 비교를 하는 것은 아니지만 정렬을 해두면 한 방향으로 탐색할 수 있다.

 

 

이제 배열에서 두개씩 item을 뽑아 더하여 주어진 수 X와 같은지 비교해나가면 된다.

앞에서부터 하나씩 선택하면서 모든 경우의 수를 따지듯 loop를 돌릴 수도 있겠지만 배열의 크기가 100,000개 이므로 시간초과를 피하기 위해서는 다른 방법을 찾아야 한다.

 

 

오름차순으로 정렬된 배열에서 맨 앞과 맨 뒤의 숫자를 시작으로 두 수를 뽑아보면 어떨까?

목표 값과 대소 비교를 통해서 쉽게 다음 숫자를 선택할 범위를 정할 수 있을 것이다.

 

 

 

 

그림과 같이 두개의 포인터로 시작과 끝점을 가리키고 두 값을 더해 목표 값인 X와 비교한다.

다음 값을 탐색하는 방법에는 왼쪽 포인터를 이동하는 방법과 오른쪽 포인터를 이동하는 방법이 있다.

 

 

배열은 오름차순으로 정렬되어있기 때문에 왼쪽 포인터를 이동시키면 두 수의 합은 커진다.

반대로 오른쪽 포인터를 왼쪽으로 이동시키면 두 수의 합은 작아진다.

 

 

목표 값 X와 비교할 때 Two pointer의 수의 합이 더 작은 경우 왼쪽 포인터를 이동시키고, 더 큰 경우 오른쪽 포인터를 이동시키는 방식으로 탐색하면 상당히 빠르게 배열의 모든 요소를 탐색해서 원하는 조건의 쌍을 구할 수 있다.

 

 

이처럼 1차원 배열에서 두개의 포인터를 이용해 값을 선택하면서 탐색하는 방법을 투 포인터 (Two Pointer) 알고리즘이라고 한다.

비슷하게 투 포인터를 이용해 범위를 표시하고 함께 이동시키면서 탐색하는  슬라이딩 윈도우 (Sliding Window) 알고리즘도 함께 알아두면 좋다.

 

 

---

 

 

전체 Code

 

#include <iostream>
#include <algorithm>

using namespace std;

int N, X;
int A[100000 + 10];

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

	int i, sum, front, back, cnt = 0;

	cin >> N;

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

	sort(A, A + N);

	front = 0;
	back = N - 1;

	while (front < back) {
		sum = A[front] + A[back];
		if (sum == X) {
			cnt++;
			front++;
			back--;
		}
		else if (sum > X) {
			back--;
		}
		else if (sum < X) {
			front++;
		}
	}

	cout << cnt << "\n";

	return 0;
}