[G3] 백준 2473번 세 용액 C++ 투 포인터, 브루트포스 알고리즘, 정렬

리뷰

 

용액 문제의 상위 버전으로 세가지 용액의 특성값의 합이 0에 가까운 케이스를 뽑는 문제

https://www.acmicpc.net/problem/2473

브루트포스 + 투 포인터를 사용한다면 최악의 경우 n^2 / 2로 n값이 10만이면 시간 복잡도상 안 돌아갈 줄 알았는데 생각보다 빠르게 실행돼서 의문이 좀 가긴 했다.

 

문제 풀이

1. 용액의 개수 n과 용액의 특성값 정보 배열 lst를 전역 변수로 설정한다. 이때 용액 세개를 더하므로 타입은 longlong
2. n을 입력 받고 lst 배열에 각 용액의 특성값을 입력받는다, 이후 오름차순으로 정렬해 준다.
3. 정답 출력용 al, am, ar 변수를 초기화 하고 ans값을 30억으로 설정해 준다, ans도 longlong타입으로 설정한다.
4. 첫번재 용액은 브루트포스를 통해 0 ~ n - 3인덱스를 고정으로 탐색을 시작해 준다.
5. left는 i + 1, right는 n - 1로 투 포인터를 실행해 준다, while 조건은 left < right 일때 이다.
6. sum은 lst의 i, left, right 인덱스를 더한 값이고, 해당 값의 절댓값이 ans보다 작으면 ans값을 갱신해 준다. 이후 al을 lst의 i번째 인덱스의 값으로, am, ar을 각각 lst의 left, right 인덱스의 값으로 지정해 준다.
7. sum값이 음수면 left를 증가, 양수면 right를 감소, 0이면 탐색을 더 진행해 줄 필요가 없다.

 

 

참고 사항

용액 문제 백준 2467번

[G5] 백준 2467번 용액 C++ 투 포인터

 

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define ll long long

using namespace std;

int n;
ll lst[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> lst[i];
	sort(lst, lst + n);

	int al, am, ar;
	ll ans = 3e9;
	for (int i = 0; i < n - 2; i++) {
		int left = i + 1, right = n - 1;
		while (left < right) {
			ll sum = lst[i] + lst[left] + lst[right];
			if (ans > abs(sum)) {
				ans = abs(sum);
				al = lst[i], am = lst[left], ar = lst[right];
			}
			if (sum < 0) left++;
			else if (sum > 0) right--;
			if (sum == 0) {
				cout << lst[i] << " " << lst[left] << " " << lst[right];
				return 0;
			}
		}
	}
	cout << al << " " << am << " " << ar;
}