백준 2467번 용액

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

풀이 방법

값이 오름차순으로 들어오므로, 정렬은 필요가 없다.

정답이 가능한 경우를 생각해보자. 음수와 양수 값이 하나씩 있는 경우, 음수나 양수만 둘 있는 경우가 있다.

1. 입력에 음수나 양수 값만 있는 경우
   절대값이 가장 작은 두 값이 답이 된다.

2. 입력에 음수, 양수가 모두 있는 경우
   2-1. 입력에 음수가 둘 이상인 경우
   음수+양수가 답이거나, 절대값이 가장 작은 두 음수가 답이다.

   2-2. 입력에 양수가 둘 이상인 경우
   음수+양수가 답이거나, 절대값이 가장 작은 두 양수가 답이다.

이를 위해 음수, 양수의 개수를 세야한다. 입력이 이미 정렬된 상태로 들어오기 때문에 binary search를 이용해 쉽게 음수의 개수를 셀 수 있다.

음수의 개수가 0개나 n개라면 음수가 없거나 음수만 있는 경우이므로, 2번을 고려할 필요가 없다. 아닌 경우에 대해서만 2번을 고려한다.

2번에서 음수+양수가 답인 경우는 어떻게 풀 수 있을까? 투 포인터를 이용하자. two pointer는 시작점, 이동 방식, 종료 조건을 설정해야한다.

a. 시작점: 각 포인터는 index 0, n-1에서 출발한다.

b. 이동 방식: 두 값 중 절댓값이 더 큰 값을 줄여야한다. 즉, 더 큰 절댓값을 가리키는 포인터를 1칸 움직인다.

c. 종료 조건: 각 포인터는 음수/양수만 가리킨다.

두 포인터가 가리키는 값이 최소라면 값들을 갱신한다.

이제 1번과 2번의 음수+음수, 양수+양수가 답인 경우를 처리해주어야 하는데, 사실 같은 말이다. 음수가 2개 이상인 경우, 양수가 2개 이상인 경우만 따로 처리해주면 한번에 처리된다.

시간복잡도

binary search : O(logn)
two pointer : O(n)
total : O(logn + n) = O(n)

디버깅

1. minAbs를 2000000001로 초기화하지 않고 1000000000로 초기화하여 수정했다.
2. 투 포인터의 이동 방식을 잘못 설정하여 수정했다.

코드

#include <iostream>

using namespace std;

int n;
int acidity[100000];

/*
Count the number of negative numbers
(find the index of the minimum positive number)
by binary search
*/
int getCntNegative() {
	int retval = 0;

	if (acidity[n - 1] < 0) {
		retval = n;
	}
	else {
		int l = 0;
		int r = n - 1;
		int mid;

		while (l != r) {
			mid = l + (r - l) / 2;

			acidity[mid] < 0 ? l = mid + 1 : r = mid;
		}

		retval = l;
	}

	return retval;
}

/*
Find the minAbs of sum of one negativeand one positive
by two pointers
*/
int minAbsOfPN(int cntNegative, int *i1, int *i2) {
	int minAbs = 2000000001;

	int p1 = 0;
	int p2 = n - 1;

	int idx1, idx2, tmp;

	while (p1 < cntNegative && cntNegative <= p2) {
		if ((tmp = abs(acidity[p1] + acidity[p2])) < minAbs) {
			minAbs = tmp;
			idx1 = p1;
			idx2 = p2;
		}

		if (-1 * acidity[p1] > acidity[p2]) {
			++p1;
		}
		else {
			--p2;
		}
	}

	while (p1 < cntNegative) {
		if ((tmp = abs(acidity[p1] + acidity[cntNegative])) < minAbs) {
			minAbs = tmp;
			idx1 = p1;
			idx2 = cntNegative;
		}
		++p1;
	}

	while (cntNegative <= p2) {
		if ((tmp = abs(acidity[cntNegative - 1] + acidity[p2])) < minAbs) {
			minAbs = tmp;
			idx1 = cntNegative - 1;
			idx2 = p2;
		}
		--p2;
	}

	*i1 = idx1;
	*i2 = idx2;

	return minAbs;
}

int main(void) {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> acidity[i];
	}

	int cntNegative = getCntNegative();

	int idx1, idx2, minAbs = 2000000001;
	
	if (cntNegative != 0 && cntNegative != n) {
		minAbs = minAbsOfPN(cntNegative, &idx1, &idx2);
	}

	/*
	Check the sum of two minimum abs of two negatives or two positives
	*/
	int tmp;

	if (cntNegative >= 2) {
		if (minAbs > (tmp = abs(acidity[cntNegative - 2] + acidity[cntNegative - 1]))) {
			minAbs = tmp;
			idx1 = cntNegative - 2;
			idx2 = cntNegative - 1;
		}
	}

	if (cntNegative <= n - 2) {
		if (minAbs > (tmp = acidity[cntNegative] + acidity[cntNegative + 1])) {
			minAbs = tmp;
			idx1 = cntNegative;
			idx2 = cntNegative + 1;
		}
	}

	cout << acidity[idx1] << " " << acidity[idx2] << endl;

	return 0;
}