[백준알고리즘] 2470번: 두 용액 -C++

[백준알고리즘] 2470번: 두 용액 -C++

2470번: 두 용액 (acmicpc.net)

2470번: 두 용액

골드 5의 문제다. 정답 비율도 낮아서 생각보다 어렵나 하고 풀었는데 생각보다 훨씬 쉽게 풀리긴 했다. 예전에 비슷한 느낌의 문제를 푼 적이 있던 것 같은데, 그 덕분인지는 모르겠다. 전부터 골드 5의 문제들이 적당히 난이도 있고 풀기에 좋았던 것으로 기억한다. 그래서 진짜 어려운 문제는 아니었을 수도 있다.

---

문제 풀이

문제에서는 여러 산성도를 나타내는 값이 주어지면, 두 용액을 섞었을 때 산성도가 0에 가까워지는 두 용액을 찾아야 한다.

 

이런 문제는 Bruteforce로 찾으려면 찾을 수 있겠지만 굉장히 낭비적이라는 생각이 든다. 특히 시간제한 "1초(추가 시간 없음)"가 더욱 Bruteforce는 아니라는 냄새를 풍긴다.

 

그래서 일단은 산성도를 알칼리성과 산성을 순서대로 정렬할 필요가 있다고 느껴진다. 여기서 <algorithm>의 sort() 함수를 많이 찾아봤다. sort() 함수는 내부적으로 quick sort 방식을 사용한다고 한다. 비슷하게 stable_sort()라는 함수도 처음 알게 되었다. stable_sort() 함수는 내부적으로 merge sort 방식을 사용한다. 추가적으로 sort() 함수와 달리 같은 값이 여러 번 나오더라도, 같은 값이 처음 주어진 순서를 보장해준다고 한다.

 

여기서는 stable_sort()의 순서 보장이 딱히 필요 없기 때문에 sort() 함수를 사용했다.

 

정렬 후에 두 산성도를 고르는 방법은 다음과 같은 아이디어로 진행했다.

• 정렬된 산성도 기준으로 양쪽 끝을 기준으로 잡고, 값을 섞어본다.
• 섞은 값이 음수라면, 왼쪽 기준을 오른쪽으로 한 칸 이동한다.
• 섞은 값이 양수라면, 오른쪽 기준을 왼쪽으로 한 칸 이동한다.
• 섞은 값의 절대값이 이전에 섞었을 때의 절대값보다 작다면, 최소 절대값을 갱신한다.
• 왼쪽 기준과 오른쪽 기준이 같아지거나 교차되면 더이상 섞지 않는다.

 

섞은 값이 음수라면, 알칼리성이 산성보다 강한 것을 의미한다. 여기서 약한 산성을 골라봤자 섞은 용액은 더 큰 알칼리성을 나타낼 뿐이다. 즉, 절대값이 더 커질 수밖에 없다. 따라서 더 작은 알칼리성을 골라주어야 한다.

마찬가지로 섞은 값이 양수라면, 더 작은 산성의 용액을 골라야 한다.

 

이렇게 골라나가면 섞은 산성도 값이 0 부근에서 왔다갔다하면서 용액을 섞어볼 수 있다.

 

주어진 용액이 모두 산성이거나 모두 알칼리성일 수도 있는데, 이때도 위 아이디어를 이용하면 커버 가능하다. 모두 산성이라면 섞은 값이 양수이기 대문에 오른쪽 기준을 점차 왼쪽으로 이동시킬 것이다. 그러면 최종적으로 가장 약한 산성 용액 두 개를 고른다.(알칼리성은 반대)

 

문제를 풀고 알고리즘 분류를 보니 "두 포인터"가 있다. 아마 내가 푼 방법을 말하는 것 같다.

 

아래는 deque을 사용한 코드다.

#include <cstdio>
#include <climits>
#include <deque>
#include <algorithm>

size_t inputLiquidType();
std::deque<int> inputLiquidAcids(const int iLiquidCounts);
void sortLiquidAcids(std::deque<int> &dqAcids);
std::pair<int, int> findSmallestAbsoluteMixiedAcid(const std::deque<int> &dqAcids);

int main(void) {
	const size_t siLiquidType = inputLiquidType();
	std::deque<int> dqLiquidAcids = inputLiquidAcids(siLiquidType);
	sortLiquidAcids(dqLiquidAcids);
	const std::pair<int, int> iSmallestAbsolutePair = findSmallestAbsoluteMixiedAcid(dqLiquidAcids);
	printf("%d %d", iSmallestAbsolutePair.first, iSmallestAbsolutePair.second);

	return 0;
}

size_t inputLiquidType() {
	size_t siTypes = 0;
	scanf("%zu", &siTypes);
	return siTypes;
}

std::deque<int> inputLiquidAcids(const int iLiquidCounts) {
	std::deque<int> dqAcids;
	for ( int iCnt = 0; iCnt < iLiquidCounts; ++iCnt ) {
		int iAcid = 0;
		scanf("%d", &iAcid);
		dqAcids.push_back(iAcid);
	}
	return dqAcids;
}

void sortLiquidAcids(std::deque<int> &dqAcids) {
	std::sort(dqAcids.begin(), dqAcids.end());
}

std::pair<int, int> findSmallestAbsoluteMixiedAcid(const std::deque<int> &dqAcids) {
	unsigned int uiSmallestAbsoluteValue = UINT_MAX;
	std::pair<int, int> pairSmallestAbsolute;
	size_t siLeft = 0;
	size_t siRight = dqAcids.size() - 1;

	while ( siLeft < siRight ) {
		const int iMixiedValue = dqAcids[siLeft] + dqAcids[siRight];
		const unsigned int uiMixiedAbsolute = ::abs(iMixiedValue);

		if ( uiMixiedAbsolute < uiSmallestAbsoluteValue ) {
			uiSmallestAbsoluteValue = uiMixiedAbsolute;
			pairSmallestAbsolute = std::make_pair(dqAcids[siLeft], dqAcids[siRight]);
		}

		if ( iMixiedValue < 0 ) {
			siLeft++;
		}
		else {
			siRight--;
		}
	}

	return pairSmallestAbsolute;
}