[C++] 백준 2467번 - 용액

 

 

문제 2467번

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

2467번: 용액

 

오늘은 투포인터를 사용하는 문제를 골랐다!! 투 포인터는 오름차순으로 정렬된 데이터를 양끝(left, right)에서부터 시작하여 탐색하는 방법이다.
이 문제에서 입력값이 오름차순으로 들어오기 때문에 따로 정렬은 안 해줘도 된다. left와 right에는 각각 첫번째 인덱스와 마지막 인덱스인 0과 N-1로 초기화시켜준다. while문을 이용하여 left와 right가 바로 옆일 경우까지 계속 반복시켜주는데 그 안에서는 Min과 Max값을 각각 넣어주고 이를 더해준 sum을 이용한다. 만약 sum의 절댓값이 temp에 미리 저장한 양끝값을 더한 절댓값보다 작으면 temp에 넣어주고 Min과 Max도 해당 left, right가 인덱스인 값으로 바꿔준다. sum이 0보다 큰 경우에는 작은 수를 더해야하기 때문에 right를 1감소시켜주고, 0보다 작은 경우에는 큰 수를 더할 필요가 있기 때문에 left를 1증가시켜준다. 만약에 합이 0일 경우 0에 가장 가까운 경우이기 때문에 break로 탐색을 중단하고 바로 두 용액을 출력한다.

 

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

int main() {
	int N;
	cin >> N;
    vector <int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	int left = 0, right = N - 1;
	int Min = v[left];
	int Max = v[right];
	int temp = abs(Min + Max);
	while (left < right) {
		int sum = v[left] + v[right];

		if (temp > abs(sum)) {
			temp = abs(sum);
			Min = v[left];
			Max = v[right];
		}
		
		if (sum > 0) {
			right--;
		}
		else if (sum < 0) {
			left++;
		}
		else {
			break;
		}
	}
	cout << Min << ' ' << Max;

	return 0;
}