[이진 탐색(Binary search)] 예제 문제2: 두 용액_백준

이진 탐색 문제는 탐색의 대상을 찾는 것이 중요하다.
이전 포스팅의 문제들은 이진탐색을 하는 과정에서 mid의 값이 결정될 때 마다 해당 mid를 바탕으로 요구조건을 충족하는지에 대한 판단이 있었다. 따라서 시간 복잡도가 O(logN) * O(k)와 같았다.

반면 아래 문제는 반복문 안에서 이진탐색이 이루어지는 경우이다. 시간 복잡도는 O(n) * O(logn)이다.

---

문제 1. 두 용액

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

int N;

pair<int, int> solution(vector<int>& SOL) {
	// 먼저 용액 벡터를 정렬한다.
	// O(nlogn)
	sort(SOL.begin(), SOL.end());

	int minBalance = 2 * 1e9;
	pair<int, int> minPair;

	// 각 용액을 기준으로 잡고 합쳤을 때 가장 0에 가까운 용액을 탐색한다.
	for (int i = 0; i < N; i++) {
		int nowSol = SOL[i];

		int start = 0;
		int end = N - 1;
		bool leftFlag = false;
		bool rightFlag = false;
		while (start <= end) {

			int mid = (start + end) / 2;

			// 자기자신이라면 (예외 처리) ////////////////////////////
			bool moveleft = false;
			bool moveright = false;

			if (mid == i) {	
				// 자신의 왼쪽 또는 오른쪽을 선택하도록 한다. 

				// 만약 왼쪽에 용액이 존재한다면,
				if (i - 1 >= 0) {
					if (leftFlag == false) {
						leftFlag = true;	// 왼쪽 용액에 방문 표시
						mid = mid - 1;

						moveleft = true;
					}
				}
				if (moveleft == false) {
					// 왼쪽을 선택하지 못함
					if (rightFlag == false) {
						rightFlag = true;
						mid = mid + 1;

						moveright = true;
					}
				}
				// mid가 자기 자신인데 왼쪽 오른쪽 아무곳도 가지못한다면 break;
				if (moveright == false)
					break;
			}
			/////////////////////////////////////////////////


			// 이진탐색으로 탐색한다.
			// 하나의 용액과의 합이 양수이다 -> mid를 왼쪽으로 이동
			// 하나의 용액과의 합이 음수이다 -> mid를 오른쪽으로 이동 
			// 가장 영과 가까운 값을 갱신한다.

			int compSol = SOL[mid];
			
			if (nowSol + compSol > 0) {
				// mid를 왼쪽으로 이동
				if (moveright)	// mid를 처음보다 오른쪽으로 한칸더 이동했던 상태라면,
					end = mid - 2;
				else
					end = mid - 1;

				// minBalance 갱신
				if (minBalance >= nowSol + compSol) {
					minBalance = nowSol + compSol;
					minPair = { nowSol, compSol };
				}
			}
			else if (nowSol + compSol < 0) {
				// mid를 오른쪽으로 이동
				if (moveleft)
					start = mid + 2;	// mid를 처음보다 왼쪽으로 한칸더 이동했던 상태라면,
				else
					start = mid + 1;

				if (minBalance >= -(nowSol + compSol)) {
					minBalance = -(nowSol + compSol);
					minPair = { nowSol, compSol };
				}
			}
			else {	// 0보다 작을 수 없음
				minPair = { nowSol, compSol };
				return minPair;
			}

		}
	}
	

	return minPair;
}

int main() {
	cin >> N;

	// 용액 벡터
	vector<int> SOL(N);
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		SOL[i] = x;
	}

	pair<int, int> minPair = solution(SOL);
	if (minPair.first < minPair.second)
		cout << minPair.first << " " << minPair.second << endl;
	else
		cout << minPair.second << " " << minPair.first << endl;
	return 0;
}

2022/06/17 풀이

이미 선택한 용액을 다시 한번 선택했을 때의 처리 코드 간결화

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

const int MAX_INT = 2 * 1e9;


bool moveLeftOrRight(int nowIdx, const vector<int>& SOL) {
	if (nowIdx <= 0)
		return false;	// 오른쪽 이동
	else if (nowIdx >= SOL.size() - 1)
		return true;	// 왼쪽 이동

	if (abs(SOL[nowIdx] + SOL[nowIdx - 1]) > abs(SOL[nowIdx] + SOL[nowIdx + 1])) {
		// 오른쪽 이동
		return false;
	}
	else {
		// 왼쪽 이동
		return true;
	}
}

bool moveLeftOrRight(int nowSol, int otherSol) {
	if (nowSol + otherSol > 0)
		return true;
	else
		return false;
}

pair<int, int> solution(int n, vector<int>& SOL) {
	// 이진탐색을 위한 정렬
	sort(SOL.begin(), SOL.end());

	pair<pair<int, int>, int> answer = { {SOL[0], SOL[n-1]}, MAX_INT };

	for (int i = 0; i < n; i++) {
		int nowSol = SOL[i];

		// nowSol과의 합이 0과 가장 가까운 용액찾기
		int start = 0;
		int end = n - 1;

		pair<pair<int, int>, int> temp = { {SOL[start], SOL[end]}, MAX_INT };
		while (start <= end) {
			int mid = (start + end) / 2;

			// 선택된 용액이 다시 선택될 때
			if (i == mid) {
				if (moveLeftOrRight(i, SOL))
					end = mid - 1;
				else
					start = mid + 1;
			}
			// 
			else {
				int otherSol = SOL[mid];
				if (nowSol + otherSol == 0)
					return { SOL[i], SOL[mid] };

				if (moveLeftOrRight(nowSol, otherSol)) {
					// 왼쪽 이동
					end = mid - 1;
				}
				else {
					// 오른쪽 이동
					start = mid + 1;
				}

				if (temp.second > abs(nowSol + otherSol))
					temp = { {SOL[i], SOL[mid]}, abs(nowSol+otherSol) };
			}
		}

		if (answer.second > temp.second) {
			answer = temp;
		}
	}

	return answer.first;
}

int main() {
	int n;
	cin >> n;

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

	pair<int, int> answerPair = solution(n, inputVec);
	cout << answerPair.first << ' ' << answerPair.second << endl;
	
	return 0;
}