백준 3273번 두 수의 합 C++ 투 포인터, 정렬

리뷰

배열내 요소를 조합하여 특정 숫자를 만족하는 조합의 개수를 찾기

https://www.acmicpc.net/problem/3273

 

 

문제 풀이

1. n을 입력 받고 배열 arr에 n개의 수를 입력 받아준다. 이후 목표 숫자 target을 입력 받고 arr 배열을 정렬해 준다.
2. 개수를 샐 변수 cnt를 0으로, 왼쪽에서 탐색할 left 변수를 0으로, 오른쪽에서 탐색할 right 변수를 n - 1로 초기화 한다.
3. left가 right보다 적을 때 while 루프를 실행한다.
4. arr[left]와 arr[right]를 더했을 때 target보다 크다면 right를 1 줄여준다.
5. arr[left]와 arr[right]를 더했을 때 target보다 작다면 left를 1 늘려준다.
6. 만약 target을 찾았다면 cnt를 1 증가시키고 right를 1 감소, left를 1 감소한다.
7. while루프가 종료될 때 까지 탐색을 계속하고, 종료 되었다면 cnt를 출력해 준다.

 

참고 사항

정렬은 오름차순이던 내림차순이던 상관 없다.

 

 

정답 코드

#include<iostream>
#include<algorithm>

using namespace std;

int n, target;
int arr[100001];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	cin >> target;
	sort(arr, arr + n);
	int cnt = 0, left = 0, right = n - 1;
	while (left < right) {
		if (arr[left] + arr[right] > target) right--;
		else if (arr[left] + arr[right] < target) left++;
		else {
			cnt++;
			left++;
			right--;
		}
	}
	cout << cnt;
}