36. UVa-10487 Closest Sums //nlogn solution

문제

<그림1: 문제 설명>

 

문제는 n개의 원소로 이루어진 입력이 주어졌을 때 들어오는 또 다른 input인 query에 대해 n개의 입력 중 두 원소를 더한 sum이 query에 제일 가까운 sum을 구하는 것이다.

 

Competitve Algorithm책에서는 가능한 모든 sum을 보는 O(n²)풀이를 제시하고 있는데, 사실 정렬을 제외한 파트를 O(n)안에 구현하는 방법도 있다. (오버헤드와 사용공간이 좀 늘어나지만) 다음<그림2>를 보자.

 

<그림2: 문제 풀이 논리>

우선, 들어온 n개의 input에 대해 nlgn시간 안에 Sorting을 하자. 그 후 배열의 시작원소를  start, 끝 원소를 end로 두자.

이후 반복문을 돌리는데 각 step에서 input[start]+input[end]를 sum으로 평가한 후 sum<query이면 ++start, sum>query이면 --end를 하면 sum이 query에 점점 가까워지게 되고 이런 Logic으로 Start==end인 상황이 되기 전까지 step을 반복하면 input에서 가능한 모든 _nC₂가지의 sum 중 solution을 포함한 n개의 sum들을 다 볼 수 있다. 

또한, 이 반복은 루프 하나로 가능하므로 n-time을 갖게 된다. 가능한 모든 조합을 보는 것보다는 시간복잡도면에서 빠르다. 이 때 각 loop에서 새로 평가된 sum에 대해 |sum-query|가 제일 작은 sum을 OptimalSum으로 갱신하면 최종 Step이후 그것이 해가된다.

코드는 다음과 같다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int main() {

	int n, m,sum,temp,start,end,optimalSum,cases=0;
	int input[1000];
	int query;
	while (cin >> n && n != 0) {
		for (int i = 0; i < n; i++) cin >> input[i];
		sort(input, input + n);
		cin >> m;
		cout << "Case " << ++cases << ":" << endl;
		for (int i = 0; i < m; i++) {
			cin >> query;
			start = 0; end = n - 1;
			sum = 0; optimalSum = 0; temp = abs(query-input[start] - input[end]);
			while (start != end) {	//O(n)
				sum = input[start] + input[end];	//calc new step's sum
				if (abs(query - sum) < temp) {
					optimalSum = sum;
					temp = abs(query - sum);
				}
				if (sum < query) ++start;
		
				else if (sum > query) --end;
				
				else {
					optimalSum = sum;
					break;
				}
			}
			cout << "Closest sum to " << query << " is " << optimalSum << "."<<endl;
		}
	}

	return 0;
}

 

오버헤드와 사용공간이 늘어나지만 O(n²)보다는 훨씬 효율적인 해라고 생각한다.