[백준] 두 수의 합(C++)

comomo·2024년 4월 10일

코딩연습

목록 보기

15/28

문제

문제설명
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다.
자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.

문제분석
중복되는 값이 없는 수열에서 두 값을 더했을때 S가 되는 쌍의 개수를 구하면 된다.

투포인터

1차원 배열에서 두개의 포인터를 조작하며 답을 구해가는 방법이다.
아래의 링크에 설명이 잘 되어있다.
유튜브

해결방법

수열을 우선 정렬한후에 수열의 양끝에서 부터 값을 더해가며 합이 S인지 확인한다.

시간초과

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	int num;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> num;
		v[i] = num;
	}
	int s;
	cin >> s;
	int size = v.size();
	int count = 0;
	sort(v.begin(), v.end());
	for (int i = 0; i < size - 1; i++) {
		int want = s - v[i];
		for (int j = v.end() - v.begin() - 1; j > i; j--)
		{
			if (v[j] == want) count++;
			else if (v[j] < want) break;
		}
	}
	cout << count;
		

}

위와 같은 방식으로 작성후 제출 하였을때 시간초과가 발생했다.
i,j를 각각의 포인터로 설정하였는데 위의 방식은 i가 증가할때마다 j가 끝으로 되돌아가기 때문에 시간제한을 만족하지 못한것 같다.

이를 수정한 코드이다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	int num;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> num;
		v[i] = num;
	}
	int s;
	cin >> s;
	int count = 0;
	sort(v.begin(), v.end());
	int start = 0;
	int end = v.size() - 1;
	
	while(start < end)
	{
		if (s == v[start] + v[end]) {
			count++;
			start++;
		}
		else if (v[start] + v[end] < s) start++;
		else end--;
	}
	cout << count;		

}