[백준알고리즘] 1715번: 카드 정렬하기 -C++

[백준알고리즘] 1715번: 카드 정렬하기 -C++

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

그리디 알고리즘을 몇 개 풀어보면서 느낀 게, 참 SJF 방식만 알면 모든 문제가 쉽게 생각되는 것 같다. 그만큼 SJF가 대표적인 그리디적인 방식인 것이기도 하지만 말이다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

우선, 카드의 개수를 봤을 때 굳이 배열을 안 쓰고 map을 써도 시간이 충분하겠다고 생각이 들었다. map과 set은 최솟값을 찾기 쉬워 쉽게 우선순위 큐의 특징을 사용할 수 있다. 하지만, 그만큼 추가/삭제에도 비용이 든다. 그런데, 문제에서 주어진 입력의 개수는 map의 원소의 추가/삭제에 비용이 치명적이지 않을 것이라 생각됐다.

 

그리고 자연스럽게 그리디 방식을 적용해 문제를 풀었다. 현재 합쳐지지 않은 가장 작은 크기의 덱을 두 개 선택한다. 두 덱의 크기가 각각 \(A\)와 \(B\)라고 할 때, 두 덱을 합치는데 들어가는 비용은 \(A+B\)이다. 그러면 \(A+B\) 크기의 덱이 하나 생기게 되는데, 이 합쳐진 덱을 다시 합쳐지지 않는 덱들 사이에 두는 방식으로 진행한다.

 

그리고, 두 가지 주의해야할 점이 있다.

• 같은 크기의 덱이 여러개 존재할 수 있다.
  • 따라서 set을 사용할 경우, 크기가 중복되는 두 덱을 확인할 수 없다.
• 덱이 1개만 남개된다면, 덱을 합치는 일이 발생하지 않기 때문에 비용이 0이다.
  • 처음부터 1개만 있더라도 마찬가지다.

 

이 두가지만 주의하면, 문제를 쉽게 풀 수 있다.

아래는 통과한 코드다.

#include <cstdio>
#include <map>

int main(void) {
	/* 입력 */
	int N;
	scanf("%d", &N);

	std::map<int, int> mapCardSet;
	for ( int iSet = 0; iSet < N; ++iSet ) {
		int iCard = 0;
		scanf("%d", &iCard);

		std::map<int, int>::iterator itCardSet(mapCardSet.find(iCard));
		if ( mapCardSet.end() == itCardSet ) {
			mapCardSet.insert(std::make_pair(iCard, 1));
		}
		else {
			itCardSet->second++;
		}
	}

	/* 계산 */
	int iTotalCompare = 0;
	while ( (0 < mapCardSet.size() && 2 <= mapCardSet.begin()->second) || 2 <= mapCardSet.size() ) {
		int iSmallest = 0;
		int iSmaller = 0;

		// 가장 작은 덱의 크기가 중복인 경우
		if ( 2 <= mapCardSet.begin()->second ) {
			iSmallest = iSmaller = mapCardSet.begin()->first;
			mapCardSet.begin()->second -= 2;

			if ( 0 == mapCardSet.begin()->second ) {
				mapCardSet.erase(mapCardSet.begin());
			}
		}
		// 가장 작은 크기와 그 다음 작은 크기의 덱을 합치는 경우
		else {
			iSmallest = mapCardSet.begin()->first;
			mapCardSet.erase(mapCardSet.begin());

			iSmaller = mapCardSet.begin()->first;
			mapCardSet.begin()->second--;

			if ( 0 == mapCardSet.begin()->second ) {
				mapCardSet.erase(mapCardSet.begin());
			}
		}

		// 두 덱을 합치는데 비교하는 횟수
		int iCompare = iSmaller + iSmallest;
		// 합친 덱을 다시 비교 대상에 추가
		std::map<int, int>::iterator itMergeSet(mapCardSet.find(iCompare));
		if ( mapCardSet.end() == itMergeSet ) {
			mapCardSet.insert(std::make_pair(iCompare, 1));
		}
		else {
			itMergeSet->second++;
		}

		// 전체 비교 횟수 갱신
		iTotalCompare += iCompare;
	}

	/* 출력 */
	printf("%d", iTotalCompare);

	return 0;
}