[G5] 백준 2470번 두 용액 C++ 투 포인터, 정렬

리뷰

 

간단한 이분탐색 문제

 

 

전역 변수

• n : 주어지는 수열의 길이
• o, t : 섞었을 때 0과 가장 가까운 두 용액을 저장할 변수
• ans : 여태 까지 나온 0과 가장 가까운 수를 저장하기 위한 변수
• lst : 수열의 정보를 입력받기 위한 정수형 배열

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, 길이가 n인 수열의 정보를 lst에 입력 받아준다.
2. lst의 요소를 오름차순으로 정렬해 준다.
3. l, r을 각각 수열의 맨 앞과 맨 뒤의 인덱스로 지정해 준다.
4. l과 r이 동일해 질 때까지 반복문을 실행한다.
5. lst의 l, r인덱스의 값을 더한 값을 정수형 변수 val에 저장해 준다.
6. val의 절대값이 ans의 절대값보다 작다면 ans를 val로 저장하고, o를 lst[l]로, t를 lst[r]로 변경해 준다.
7. 이후 val이 0보다 크다면 r의 인덱스를 감소시킨다.
8. val이 0보다 작다면 l의 인덱스를 증가시킨다.
9. val이 0이라면 더 이상 탐색할 필요가 없으니 break를 해준다.

 

 

참고 사항

현재는 탐색이 O(N)이지만 이분 탐색을 사용하면 O(LogN)으로 더 빠르게 탐색할 수 있을 것 같다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, o, t, ans = 2e9;
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 l = 0, r = n - 1;
	while (l < r) {
		int val = lst[l] + lst[r];
		if (abs(val) < abs(ans)) {
			ans = val;
			o = lst[l], t = lst[r];
		}

		if (val > 0) r--;
		else if (val < 0) l++;
		else break;
	}

	cout << o << " " << t;
}