✨3273번. 두 수의 합._2번째 투포인터 풀이

phoenixKim·2022년 7월 30일

백준 알고리즘

목록 보기

50/174

알고리즘 분류

: 2번째 투포인터 풀이

주의할 점.

두 개의 포인터를 이용해서 원소를 비교하는 것이므로,
조건문은 반드시 등호 없어야 함.

왜 두번째 투포인터 풀이를 생각해내야 하냐면 ?

컨테이너를 고정하라는 말이 없음.
오름차순으로 했을 때, 가장 작은 것은 왼쪽에, 가장 큰값은 오른쪽에 있음.
중복되는 값이 없다고 함. (중복되도 상관을 없음.)

큰돌님의 투포인터 사진을 떠올리자.

https://blog.naver.com/jhc9639/222319124359

풀이전략

: 아무생각 없이 할 경우, n * n의 시간복잡도임.

정렬한 후, 양 끝점을 이용해 가운데로 이동시키는 방법으로 풀 수 있음.
왜? 문제에서 중복되지 않는다고 했고, 쌍을 구하는 것이므로,
정석적인 투포인터로는 풀 수 없음. 왜냐하면, 반례가 발생함.

3과 10에서 카운팅을 한 다음에 start와 end 값 변경 후에, 5 7 9에서
왔다리 갔다리 문제가 발생함.

-> 2번째 투포인터 코드를 사용해야 함.
: right를 앞쪽으로 댕기는..

나랑 동일한 생각을 하신 분
https://www.acmicpc.net/board/view/81394

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;


	
int main() 
{
	// 두 개의 원소를 더했을 때
	// 합이 x가 나오는 것을 찾는 문제임.
	
	// 생각할 점 : 수열의 크기 n 의 범위가 100만임.
	// 2중 포문 돌려서 하려면 
	// 100만 * 100만 불가함. 

	// 투포인터를 사용하자. 
	// but, 연속된 값이 아닌데... 

	int n;
	cin >> n;
	vector<int>v(n);

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

	int x;
	cin >> x;

	sort(v.begin(), v.end());

	//for (int i = 0; i < n; ++i) 
	//{
	//	cout << v[i] << endl;
	//}

	// 일반적인 투포인터는 연속된 값을 처리하게 되지만...
	// 0번 인덱스와 마지막 인덱스 부터 첫 단추를 뀌어서
	// 원하는 수가 동일할 경우에 l값을 증감한다던지
	// r값을 처리한다던지 하자.
	
	// 왜 투포인터로 했냐면? 
	// 이중포문으로 돌리면, n * n 의 시간복잡도 이지만, 
	// 투포인터의 경우의 시간복잡도를 구해보자..

	int l = 0, r = n - 1;
	int ret = 0;
	while (l < r)
	{
		//위에서 어차피 정렬을 했으니까...
		if (v[l] + v[r] == x)
		{
        // 왜 이렇게 했냐면, 문제의 조건에서 중복된 값이 없다고 했으니까.
        // 동일한 값을 r과 l 처리를 하고 있는 것임.
			++ret;
			--r;
            ++ㅣ;
		}
		else if (v[l] + v[r] < x)
		{
			++l;
		}
		else if (v[l] + v[r] > x)
		{
			--r;
		}
	}

	cout << ret;
}