처음 boj 2467번 문제에 대해서 풀이를 생각해보았을때, 이분탐색을 이용한 풀이에 대해서 생각하였고,
그 풀이를 구현하는데 있어서 참고 코드를 보게되었는데, 참고 코드의 경우 lower_bound를 사용해서 인덱스 값을 구하고, 각각의 경우에 대해서
idx-1, idx, idx+1의 경우들로 나누어서 값을 갱신해주는 형태로 작성된 코드였다.
그 코드를 첨부해보면,
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[100005];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int ans1 = 1e9+1;
int ans2 = 1e9+1;
for(int i = 0; i < n; i++){ // -a[i]에 대한 lower_bound를 구할 예정
int idx = lower_bound(a, a+n, -a[i]) - a; // lower_bound의 성질에 따라 a[idx]는 -a[i]와 같거나, -a[i]보다 큰 원소 중에 가장 작은 원소이다.
// a[i]와 더했을 때 값이 가장 작은 원소는 a[idx+1] 혹은 a[idx] 혹은 a[idx-1]이다.
if(idx+1 < n && i != idx+1 && abs(a[i] + a[idx+1]) < abs(ans1 + ans2)){
ans1 = a[i];
ans2 = a[idx+1];
}
if(idx < n && i != idx && abs(a[i] + a[idx]) < abs(ans1 + ans2)){
ans1 = a[i];
ans2 = a[idx];
}
if(idx != 0 && i != idx-1 && abs(a[i] + a[idx-1]) < abs(ans1 + ans2)){
ans1 = a[i];
ans2 = a[idx-1];
}
}
if(ans1 > ans2) swap(ans1, ans2); // 출력 형식에 맞게 설정
cout << ans1 << ' ' << ans2;
}
/*
만약 같은 용액을 두 번 사용하는게 허용된다면 a[idx+1]은 고려하지 않아도 된다. 그러나 이 문제에서는 같은 용액을 두 번 사용할 수 없다는 조건이 있어서 a[i]와 더했을 때 값이 가장 작은 원소가 a[idx+1]일 수 있다.
예시 -> 수열 -100 1 10 14에서 i = 1일 때 idx = 1이고, a[1] + a[idx+1]이 가장 작다.
*/이러한 형태의 풀이였는데, 처음 이 코드를 접했을때, 3가지 경우를 나누어서 생각해주는 것에 대해서 약간 이해가 안가는 부분이 있어서 다른 풀이들에 대해서 검색해보게 되었다.
그래서 접하게 된 것이 투 포인터를 활용한 풀이이고, 그 풀이 방법을 코드로 작성해 보자면,
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100'005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
int ans=2*1e9+1;
int st=0;
int en=n-1;
int ans1, ans2;
while(st<en){
int cur=a[st]+a[en];
int num=abs(cur);
if(num<ans){//num= abs(cur)로 정의된 수이기 때문에, 최소값은 0이다.
ans=num;
ans1=a[st];
ans2=a[en];
}
if(cur>0) en--;
else st++;
}
cout<<ans1<<' '<<ans2;
}이러한 형태의 풀이이다.
일단 처음에 생각할때는 이분탐색이 절반씩 줄여가는 형태로 작성하니까 더욱 빠를것이다 라는 생각을 하였는데,
막상 이분탐색을 이용한 풀이, 그리고 투 포인터를 이용한 풀이를 모두 제출해보고 소요 시간에 대해서 확인해보니까 모두 동일하게 16ms로 빠르게 동작하는걸 확인할 수 있었다.
그래서 곰곰이 생각해보니 투포인터의 경우는 선형탐색과 동일한 시간을 나타내줄 것이고,
이분탐색 알고리즘은 for문을 통해서 n번 돌고, 그리고 각각에 대해서 이분탐색을 통해서 idx를 찾아야 하니까 lgN이 걸릴것이라는 생각을 하게되었다.
그래서 각각의 코드를 gpt를 통해서 시간복잡도에 대한 분석을 해보았다.
첫번째- 이분탐색 lower_bound를 통한 풀이의 시간 복잡도에 대하여.
두번째- 투 포인터를 이용한 풀이의 시간 복잡도에 대하여.
따라서 처음 막연하게 이분탐색은 절반씩 줄여가면서 탐색을 하니까 더 빠를것이다 라는 생각과는 다르게,
결국 이분탐색을 for 문을 통해서 n번 반복하기 때문에 이 풀이의 경우는 n long n의 시간 복잡도를 가지기 때문에, 투 포인터를 이용한 풀이가 시간 복잡도 측면에서는 더욱 유리한 형태를 가지게 된다.
그리고 풀이를 작성하고 이해하는 측면에서도 이분탐색을 활용하는 것보다는 투 포인터를 이용한 풀이가 더욱 이해하기 쉽고 간결한 코드를 보여준다고 생각한다.
현재는 이분탐색 위주로 풀이를 연습하고 공부하고 있고, 투 포인터에 대한 공부와 문제풀이는 다음 단원에서 공부할 것이기 때문에 아직 투포인터 풀이에 대해서 익숙치 않은 모습을 보이지만, 다음 단원에 공부할때 확실하게 익숙해지도록 하고, 이런 문제를 만나면 두가지 풀이법을 생각해냈을때 더욱 간결하고 시간복잡도가 작을만한 풀이를 생각해서 그 풀이를 적용시킬 수 있도록 해보자.
++++++++
투 포인터 풀이를 참고한 정리가 깔끔하게 되어있는 블로그 풀이
https://velog.io/@soosungp33/BOJ-2467%EB%B2%88-%EC%9A%A9%EC%95%A1C
[BOJ] 2467번 : 용액(C++)
투 포인터
velog.io
