백준 2470번 - 두 용액, 대표적인 투 포인터 문제

문제 소개

2470번 두 용액 문제는 제목에도 쓰여있는 것처럼 대표적인 투 포인터 알고리즘으로 풀이 가능한 문제 중 하나입니다!

 

solved.ac 기준으로 골드 5 난이도의 문제로 기본적인 투 포인터 문제임에도 불구하고 꽤 높게 난이도가 책정되어 있습니다.

 

문제 링크입니다!! 😀

2470번: 두 용액

---

문제 설명 및 아이디어

우선 입력으로 용액의 개수인 N을 입력 받은 후, 산성 용액(특성 값이 양의 정수)와 알칼리성 용액(특성 값이 음의 정수) 들의 특성 값을 임의의 순서대로 입력받습니다.

 

이렇게 입력받은 용액들 중에서 임의로 두 개를 선택했을 때, 두 용액의 특성 값의 합이 0에 가장 가까운 경우 선택한 두 개의 용액의 특성 값을 반환하는 간단한 문제입니다!! 😀

 

예제 입력

5
-2 4 -99 -1 98

예제 출력

-99 98

위의 예제 입력의 예시에서는 -99와 98의 특성 값에 해당하는 용액을 선택해야 -1로 0에 가장 가까운 조합을 선택할 수 있게 되는 구조입니다.

 

따라서 저는 이 문제를 해결하기 위해서 hi라는 포인터(인덱스)를 이용해 가장 높은 특성 값의 용액을 가리키고 lo라는 포인터(인덱스)를 이용해 가장 낮은 특성 값의 용액을 가리켜서 이 두 개의 포인터를 현재 두 용액의 특성 값의 합으로 기반으로 적당히 조절하여 최적의 조합을 찾고자 하였습니다.

 

이럴 때 적용할 수 있는 개념이 바로 투 포인터 알고리즘으로 다음과 같은 개념을 적용해서 풀이를 진행했습니다.

 

투 포인터 (two pointer)

리스트 혹은 배열에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

 

e.g. 투 포인터 적용 가능한 예제들

- 두 개의 수의 합이 임의의 값에 가장 가까우려면 어떻게 두 개의 수를 선택해야 할까?

- 두 개의 수를 배열에서 임의로 뽑을 때 0에 가장 가까운 경우의 수는?

위와 같은 경우에 많이 사용되는 알고리즘이라고 간단하게 정리할 수 있습니다.

 

절댓값을 이용한 비교 연산을 진행해야

이 문제는 두 개의 특성 값의 합이 양수인지 음수인지에 관계없이 0에 가장 가까운 조합을 찾아야 하므로 합의 절댓값을 이용한 비교 연산을 진행해야 합니다.

 

예를 들어 -2, 4 두 개의 용액을 골라 2의 합이 나오는 경우와 -4, 2 두 개의 용액을 선택해 -2의 합이 나오는 경우가 똑같은 취급을 당해야 하기 때문입니다.

 

정렬을 진행한 후에 투 포인터 알고리즘을 적용해야

또한 용액의 특성 값들을 임의의 순서대로 입력받기 때문에, 먼저 입력받은 특성 값들을 정렬한 후에 투 포인터 알고리즘을 적용해 풀이하는 방식으로 코드를 작성해야 합니다. 

---

제출 소스 코드 (C++)

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

using namespace std;

vector<int> v;

int main() {
	int n;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	int lo = 0;
	int hi = n - 1;

	int resLo = lo, resHi = hi;

	while (lo < hi) {
		int resSub = abs(v[hi] + v[lo]);

		// 두 용액의 특성 값의 합이 더 작은 결과를 찾기 위해서 비교한다.
		if (abs(v[resHi] + v[resLo]) > resSub) {
			resHi = hi;
			resLo = lo;
		}

		if (v[hi] + v[lo] > 0) {
			hi -= 1;
		}
		else if (v[hi] + v[lo] == 0) {
			break;
		}
		else {
			lo += 1;
		}
	}

	cout << v[resLo] << " " << v[resHi];

	return 0;
}