백준 1940/c++ )) 주몽 - 투포인터 사용

처음엔 총 합을 구해서 특정 수로 나눈 답을 카운트 하는 너무너무 간단한 문제인줄 알았는데

그럼 그렇지 너무 쉽다 했다

투 포인트를 써서( 두개의 포인터 알고리즘) 풀면 답이 쉽고 빠르게 나온다

투포인터는 사용한 값은 제외하고, 순서 상관없이 두개의 합이나 중복되는 구간합을 구할때 사용하는것 같다

처음 마주한 개념이라 이해와 에러 잡기가 상당히 시간이 걸렸다 

 

아래에 투포인트를 써서 푼것과 이중 for문을 쓴 것 모두 올려보겠다

투 포인터 사용해본 코드

#include <bits/stdc++.h>
using namespace std;
int n, m;

int main(){
	int cnt=0;
	int sum=0;
	int a[15004];
	
	cin >> n;
	cin >> m;
	// 시작 요소 인덱스 
	int ptS=0;
	// 마지막 요소 인덱스  
	int ptE=n-1;
	
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	
	
	sort(a, a+n); 
	// sum 을 잘못사용. while 에서의 sum은 현재의 sum 을 복사해서 가져가 쓰므로 sum 이 갱신이 안된다 
	// sum = a[ptS]+a[ptE]; 대신 아래에서 if 조건 마다 직접 써주자 	
	// 앞의 포인터가 뒤의 포인터와 만나기 전까지 실행   
	while(ptS<ptE){
		if(a[ptS]+a[ptE]==m){
			cnt++;
			ptS++;
			ptE--;
		}
		if(a[ptS]+a[ptE]<m){
			ptS++;
		}
		if(a[ptS]+a[ptE]>m){
			ptE--;
		}
	}
	
	cout << cnt << "\n";
	
	return 0;
}

아래는 이중 for 문을 사용한 코드이다

for 문을 사용하니 100ms 가 걸린다. 투 포인터는 8ms 로 아주 빠른 속도로 연산 한 것을 볼 수 있다

문제를 보고 투포인터를 바로바로 생각해 낼 줄 알아야 풀수있는 문제도 많아질 것이다 

#include <bits/stdc++.h>
using namespace std;
int n, m;

int main(){
	int a[15004]={0};
	int cnt=0;
	
	cin >> n;
	cin >> m;
	
	for(int i=0; i<n; i++){
		cin >> a[i];
	}	
	sort(a, a+n);
	// 이중 for문의 경우 m의 경우의 수가 15000*15000 으로 2억/2 (순서 상관없으므로 나누기 2)이 넘어서 시간 초과가
	// 날 수 있지만 m이 최대 20만 이상은 예외처리로 제외하여서 연산 시간을 줄일 수 있다  
	if(m>200000){
		cout << 0 << "\n";
	} else {
		for(int i=0; i<n; i++){
			for(int j=i+1; j<n; j++){
				if(m==a[i]+a[j]){
					cnt++;			
				}
			}
		}
		cout << cnt << "\n";
	}	
	
	return 0;
}