이번에는 백준 3273번 두 수의 합 문제를 풀어보았습니다.
수열에서 서로 다른 두 수를 골라 합이 목표값 x가 되는 경우의 수를 구해야 합니다.
배열을 정렬한 뒤 양 끝에서 시작하는 투 포인터를 사용하면 모든 쌍을 직접 확인하지 않고도 효율적으로 해결할 수 있습니다.
문제 설명
서로 다른 양의 정수로 이루어진 수열이 주어집니다.
수열에서 두 원소를 선택했을 때
ai + aj = x를 만족하는 쌍의 개수를 구하는 문제입니다.
단, 두 원소의 인덱스는 서로 달라야 하며 i < j를 만족해야 합니다.
풀이 아이디어
먼저 배열을 오름차순으로 정렬합니다.
이후 두 개의 포인터를 사용합니다.
st는 배열의 가장 작은 값을 가리킵니다.ed는 배열의 가장 큰 값을 가리킵니다.
현재 두 수의 합을 목표값과 비교하여 포인터를 이동합니다.
- 두 수의 합이 목표값보다 작다면 더 큰 값이 필요하므로
st를 증가시킵니다. - 두 수의 합이 목표값보다 크다면 더 작은 값이 필요하므로
ed를 감소시킵니다. - 두 수의 합이 목표값과 같다면 정답을 증가시키고 두 포인터를 모두 이동합니다.
문제에서 수열의 모든 값이 서로 다르다고 했기 때문에, 정답인 쌍을 찾은 뒤에는 두 포인터를 모두 이동해도 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int arr[100000];
for (int i=0; i<n; i++) cin >> arr[i];
sort(arr, arr+n);
int target;
cin >> target;
int st=0, ed=n-1, ret=0;
while(st < ed) {
if (arr[st] + arr[ed] < target) {
st++;
} else if (arr[st] + arr[ed] > target) {
ed--;
} else {
ret++;
st++;
ed--;
}
}
cout << ret;
return 0;
}풀이 흐름
-
수열의 크기와 원소를 입력받습니다.
-
배열을 오름차순으로 정렬합니다.
-
st를 배열의 시작 위치,ed를 배열의 마지막 위치로 설정합니다. -
arr[st] + arr[ed]를 목표값과 비교합니다. -
합이 작으면
st를 증가시키고, 합이 크면ed를 감소시킵니다. -
합이 목표값과 같다면 정답을 증가시키고 두 포인터를 모두 이동합니다.
-
두 포인터가 만나기 전까지 반복한 뒤 정답을 출력합니다.
구현 포인트
1. 배열 정렬
투 포인터를 사용하기 위해 배열을 오름차순으로 정렬하였습니다.
sort(arr, arr+n);배열이 정렬되어 있어야 현재 합의 크기에 따라 어느 포인터를 이동할지 결정할 수 있습니다.
2. 두 포인터 설정
int st=0, ed=n-1, ret=0;st는 배열에서 가장 작은 값을 가리키고, ed는 가장 큰 값을 가리킵니다.
따라서 처음에는 가능한 범위에서 가장 작은 수와 가장 큰 수의 합을 확인하게 됩니다.
3. 합이 목표값보다 작은 경우
if (arr[st] + arr[ed] < target) {
st++;
}현재 두 수의 합이 목표값보다 작다면 더 큰 합을 만들어야 합니다.
배열은 오름차순으로 정렬되어 있으므로, 작은 값을 가리키고 있는 st를 오른쪽으로 이동시킵니다.
ed를 왼쪽으로 이동하면 값이 더 작아져 합이 감소하므로 원하는 방향과 반대가 됩니다.
4. 합이 목표값보다 큰 경우
else if (arr[st] + arr[ed] > target) {
ed--;
}현재 두 수의 합이 목표값보다 크다면 더 작은 합을 만들어야 합니다.
따라서 큰 값을 가리키고 있는 ed를 왼쪽으로 이동시킵니다.
5. 합이 목표값과 같은 경우
else {
ret++;
st++;
ed--;
}두 수의 합이 목표값과 같다면 조건을 만족하는 쌍을 하나 찾은 것이므로 ret을 증가시킵니다.
문제에서 수열의 모든 값은 서로 다르다고 했기 때문에, 현재 st와 ed가 가리키는 값을 이용해 다른 정답 쌍이 만들어질 수 없습니다.
따라서 두 포인터를 모두 이동시켜 다음 경우를 탐색합니다.
6. 반복 조건
while(st < ed)두 개의 서로 다른 원소를 선택해야 하므로 st와 ed가 같은 위치를 가리키면 반복을 종료합니다.
st < ed 조건을 사용하면 같은 원소를 두 번 사용하는 경우도 방지할 수 있습니다.
7. 시간복잡도
배열을 정렬하는 데
O(N log N)의 시간이 필요합니다.
투 포인터 탐색에서는 st와 ed가 각각 한 방향으로만 이동하므로
O(N)의 시간이 필요합니다.
따라서 전체 시간복잡도는
O(N log N)입니다.
