[C++] 백준 2467번 - 용액
문제 접근
오름차순으로 각 용액의 특성값이 주어지는데, 두 용액을 선택해 특성값을 더했을 때 0에 가장 근접하는 두 용액의 특성값을 출력하면 되는 문제이다. 만약 그러한 두 용액 쌍이 2개 이상 존재할 경우 아무 용액 쌍이나 출력해도 된다.
모든 용액 쌍을 구해 각 합에 절댓값을 씌워 0에 가장 가까운 용액 쌍을 출력하는 단순한 방식은, N 이 용액의 개수일 때 시간복잡도 O(N^2)을 가지게 된다. 용액의 개수가 최대 100,000이므로 시간 초과를 범할 것이기에 적절하지 않은 방식이다.
이에 나는 투 포인터를 활용해 포인터를 적절하게 움직여 O(N) 시간복잡도를 가지는 알고리즘 설계를 고안했다.
시도 1 (예외가 발생하는 틀린 풀이)
(올바른 풀이를 참고하려면 바로 시도 2로 가시면 됩니다.)
단순하게 용액의 특성값 정보를 오름차순으로 담고 있는 배열의 양 끝에 left 와 right 를 배치하고, 두 합이 지금까지 구한 합보다 더 0에 가깝다면 left 를 1 증가시키고, 지금까지 구한 합보다 더 0에서 멀거나 같다면 right 를 1 감소시켜 left 와 right 가 가리키는 용액의 특성합이 0에 더 근접해지도록 포인터를 이동해주는 방식을 생각했다.
그림으로 보면 아래와 같다.
목표는 left + right 이 0에 가장 근접할 때의 left 와 right 가 가리키는 용액의 특성값을 출력하는 것이다.
우선, 가장 0에 근접할 때의 합을 담을 minimum_sum 을 선언한다. 이는 문제에서 최대 합의 절댓값은 1,000,000,000 + 1,000,000,000 이므로, 2 * 10^9 + 1로 초기화한다.
left + right = -1 이므로 minimum_sum 보다 더 0에 근접한다. 따라서 minimum_sum 을 갱신해준다.
합이 더 0에 근접하도록 하기 위해, 특성값 쌍 중 더 작은 값이 지금보다 커져야 하므로 left 의 값이 더 커지도록 left 포인터를 1만큼 오른쪽으로 shift한다.
합을 비교해보니 minimum_sum 이 더 0에 근접하므로 갱신하지 않는다.
두 합이 더 0에 근접하게 하기 위해, 특성값 쌍 중 더 큰 값이 지금보다 작아져야 하므로 right 의 값이 더 작아지도록 right 포인터를 1만큼 왼쪽으로 shift한다.
이 방식을 left 와 right 가 같아질 때까지 반복한다.
이는 실제 문제에서 명시한 출력 정해와 같지만 일부 케이스에서 틀린 답을 도출하는 잘못된 접근 방법이다.
모든 특성값이 양수로 주어졌다고 가정해보자.
위 예시의 해답은 { 1, 2 } 이다. 0에 가장 근접한 특성합은 1 + 2 = 3 이기 때문이다.
초기 minimum_sum 보다 left + right 가 0에 근접하므로 minimum_sum 을 갱신한다.
위에서는 minimum_sum 을 갱신하면 다음과 같은 로직을 수행했었다.
합이 더 0에 근접하도록 하기 위해, 특성값 쌍 중 더 작은 값이 지금보다 커져야 하므로 left 의 값이 더 커지도록 left 포인터를 1만큼 오른쪽으로 shift한다.
그렇다면 다음 step에서 포인터 위치는 아래와 같게 된다.
정해는 { 1, 2 } 인데, 이미 left 가 1의 오른쪽 위치로 움직였다.
위 로직대로 계속 수행한다면 최종 종료되었을 때의 상태는 아래와 같다.
따라서 위 방법보다 더 정교한 알고리즘을 구상해야 한다.
시도 2 (solved 풀이)
left 와 right 중 어떤 포인터를 shift할 지 정하는 과정에 그리디한 방법을 첨가하기로 하였다.
아이디어는 다음과 같다.
다음 step으로 넘어갈 때, 포인터를 shift하는 방법은 총 2가지이다.
1. left 를 오른쪽으로 1만큼 shift
2. right 를 왼쪽으로 1만큼 shift
2가지 각각의 포인터 이동을 선택했을 때, left + right 값이 더 0에 근접하는 경우를 택한다.
결국 문제에서 원하는 해는 특성합이 0에 더 근접하는 특성합 쌍을 쫓아가는 과정에서 도출되기 때문에 위와 같은 그리디한 방법이 정해가 될 수 있겠다고 판단하였다.
다음 예시를 다시 보자.
left + right 가 6이고, 이는 초기 minumum_sum 인 2 * 10^9 + 1보다 더 0에 근접하기에 minimum_sum 을 갱신해준다.
이후, left 를 shift 할 지, right 를 shift 할 지 선택하기 위해 두 경우의 특성합을 모두 비교해본다.
right 를 1만큼 왼쪽으로 shift한 경우의 특성합이 더 0에 가까우므로 right 를 1만큼 왼쪽으로 shift하는 경우를 채택한다.
위 과정을 left 와 right 가 같은 곳을 가리킬 때까지 반복한다.
가장 0에 근접하는 용액 쌍은 { 1, 2 }로, 제대로 정해를 도출함을 알 수 있다.
입력 예제
5
-99 -2 -1 4 98
출력 예제
-99 98
전체 코드
// 2467
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define endl "\n"
using namespace std;
int main(void) {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
vector<int> solution(N);
for (int i = 0; i < N; i++) {
cin >> solution[i];
}
int minimum_sum = 2e9 + 1;
int min_left = -1, min_right = -1;
int left = 0, right = N - 1;
while (left < right) {
if (minimum_sum > abs(solution[left] + solution[right])) {
minimum_sum = abs(solution[left] + solution[right]);
min_left = left;
min_right = right;
}
// 다음 어떤 포인터를 shift 할지 정함.
if (abs(solution[left + 1] + solution[right]) < abs(solution[left] + solution[right - 1])) { // left를 shift했을 때가 right를 shift했을 때보다 더 0에 가까우면 left를 shift
left++;
}
else { // 아니라면 right를 shift
right--;
}
}
cout << solution[min_left] << " " << solution[min_right] << endl;
}
풀이 후기
쉬운 문제라고 생각하고 접근했다가 사실 쉬운 놈은 나였다는걸 깨닫게 해준 문제였다..