boj 3015: 합이 0, boj 2473번: 세 용액// 두가지 문제에서 투 포인터 풀이의 차이점에 대하여.

boj 3015: 합이 0 문제의 경우 boj 2473번: 세 용액 문제의 경우와 매우 비슷한 문제라고 생각해서 이 문제의 풀이를

이분탐색이 아닌 세 용액의 풀이에 사용한 투포인터를 활용한 풀이를 사용해서 작성했었는데, 

그 풀이를 첨부해보면, 

#include <bits/stdc++.h>
using namespace std;

int n;
int a[10'005];
long long ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	for (int st = 0; st < n - 2; st++) {
		int mid = st + 1;
		int en = n - 1;
		while (mid < en) {
			int cur = a[st] + a[mid] + a[en];
			if (cur == 0) {
				ans++;
				/*cout << '(' << a[st] << ',' << a[mid] << ',' << a[en] << ')' << '\n';*/
			}
			if (cur > 0) en--;
			else mid++;
		}
	}
	cout << ans;
}

이렇게 작성 하였었고, 처음에 이렇게 작성해서 예제 입력을 했을때 정상적으로 예제 출력에 해당하는 값을 출력했다. 

그런데 이걸 제출했을때 자꾸 틀렸습니다가 나와서 일단 이분탐색을 통해서 upper_bound와 lower_bound를 사용하여서 문제를 해결하고, 현재의 투 포인터 풀이의 문제점에 대해서 생각해보았다. 

세 용액의 문제의 경우는,

if(cur>0) en--;

else mid++;

형태로 작성하던지, 

if(cur>=0) en--;

else mid++;

형태로 작성하던지 모두 정답을 출력한다. 

그런데 이 문제의 경우, 

예제를 첨부해보면, 

처음에 예제 입력으로 주어지는 

10
2 -5 2 3 -4 7 -4 0 1 -6

을 입력하면 출력값이 6 이 나오면서 정상적으로 동작하는 듯 보이나, 만약 코드를

if(cur>=0) en--;

else mid++;로 고치면 출력값이 5가 나오면서 원하는 값을 출력하지 않게 된다. 

 

코드를 if(cur>=0) en--;로 고쳤을때의 결과를 각각의 원소들까지 같이 출력해보았을때를 보면, 

(-5,2,3)이 하나 더 잡혀야 하는데 그게 잡히지 않고 있다. 

정렬되어 있는 입력값들을 쭉 나열해보자면

-6 -5 -4 -4 0 1 2 2 3 7 인데, 

여기서 

-5 2(1) 3 을 출력하고 난뒤, 이때 cur==0이 되기 때문에, 이때에 en--;이 되어서

그 다음 -5 2(2) 3 을 방문하지 못하고 en 포인터가 2 부분으로 내려와서 체크 해야할 부분을 체크하지 못하게 된다. 

그렇다면 if(cur>0) en--; 형태로 작성하면 되는거아닌가 싶겠지만, 

 

예를들어 예제입력을

9

-6 -5 -4 -4 0 1 2 3 3 으로 작성한다면, 

이때에 주어진 문제상 출력해야 할 값들은

(-6,3,3) (-5,2,3) (-5,2,3) (-4,1,3) (-4,1,3) (-4,1,3) (-4,1,3)의 7가지인데, 

이때에 if(cur>0) en--; 형태의 코드로 제출했을 때의 예제를 입력해보면, 

이렇듯 중복으로 존재하는 3에 대해서 첫번째 3(1) 으로 이루어진 합이 0이 되는 경우들을 체크해주지 못하게 된다. 

결국 en가 중복요소에 놓여있을때는 if(cur>0) 코드가 정상적으로 작동하지 않고, 

mid가 중복 요소에 놓여있을 때는 if(cur>=0) 코드가 정상적으로 작동하지 않는다. 

결국 이 코드는 중복된 요소가 있는 경우에는 정상적으로 동작할 수 없는 형태의 코드이고, 그렇기 때문에 

예제입력으로 주어지는 경우에 대해서만(en가 중복된 값을 방문할 수 있는 경우에만 정답을 제출할 수 있는 코드여서 통과한 예제 케이스) 정답을 출력할 수 있었던 틀린 풀이였다. 

 

boj 2473번 문제의 경우는 세 용액이 모두 다른 값을 나타내기 때문에 이러한 형태의 투포인터 풀이를 사용할 수 있는 형태였고, 중복원소가 나오면 이용할 수 없는 풀이라는걸 알고 확실하게 구분지어서 풀이를 활용해야 한다. 

 

현재 검색해본 부분에서 투 포인터를 활용하는 풀이가 하나 보이긴 하는데 내가 접한 코드는 코틀린으로 작성된 것이여서 아직 단박에 이해하지는 않았지만, 이제 내 풀이가 무엇이 잘못되었는지 알았으니 투포인터를 활용한 풀이를 할 수 있고, 그 부분에 대해서는 조금 더 고민해서 작성해보아야겠다. 

 

일단 이번에 세 용액, 그리고 합이 0 이라는 문제를 통해서, 투 포인터에 대한 풀이가 가능하면 투포인터를 활용하는것이 풀이도 간결하고 이해하기 쉽다는것, 그리고 중복 요소가 존재하는 경우는 투 포인터를 활용한 풀이가 잘못된 풀이가 될 수 있다는것, 그래서 풀이를 할때 투포인터의 경우는 주의해야 하고, 그냥 upper_bound, lower_bound를 이용해서 중복 요소의 시작과 끝 위치를 파악해서 문제를 푸는것이 더 나을 수 있다는것을 알아두도록 하자.