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

리뷰

 

두 용액의 합이 0과 가장 가까워 지는 순서쌍을 출력하는 문제

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

 

문제 풀이

1. 용액의 개수 n과 용액의 특성값을 저장할 lst배열을 용액의 최대치 만큼의 크기로 설정한다.
2. n값을 입력 받고 n개의 용액의 특성값을 lst배열에 저장해 준 후 lst배열을 오름차순으로 정렬해 준다.
3. left는 0부터 right는 n - 1부터 탐색을 시작하고 정답을 출력할 al, ar를 초기화 하고 ans는 매우 큰 값으로 초기화 한다.
4. left가 right보다 작을때만 탐색을 진행해 준다. lst의 left와 right 인덱스를 더한값을 sum에 저장해 준다.
5. sum의 절댓값이 ans보다 작으면 ans를 갱신시켜 준다, 만약 0일 경우 바로 탐색을 종료한다.
6. ans가 갱신되거나 sum이 0일 경우 ar, al에 lst의 left, right인덱스의 값을 넣어주면 된다.
7. sum이 0보다 작으면 left를 증가하고 sum이 0보다 크면 right를 감소시켜 준다.
8. 탐색이 완료된 후 al과 ar을 공백으로 구분하여 출력해 주면 된다.

 

참고 사항

이분탐색이 아닌 투 포인터로 문제를 풀어도 충분히 시간 내에 AC를 받을 수 있다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n;
int 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 left = 0, right = n - 1;
	int al, ar, ans = 2e9;
	while (left < right) {
		int sum = lst[left] + lst[right];
		if (ans > abs(sum)) {
			ans = abs(sum);
			al = lst[left], ar = lst[right];
		}
		if (sum < 0) left++;
		else if (sum > 0) right--;
		else {
			al = lst[left], ar = lst[right];
			break;
		}
	}
	cout << al << " " << ar;
}