[Baekjoon Online Judge] 백준 1715번 카드 정렬하기(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1715번 카드 정렬하기

(C++, Python)

(글쓴날 : 2020.04.27)

 

---

* Baekjoon Online Judge, 백준 1715번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1715번 카드 정렬하기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

N개의 정렬된 숫자 카드 묶음이 주어지고, 각 숫자 카드들을 모두 하나로 합칠 때 최소 비교 횟수를 구하는 문제입니다.

 

저의 경우, 우선순위 큐를 적용하였으며, C++과 Python을 사용했습니다.

처음에 문제를 제대로 이해하지 못해서 헷갈렸던 부분이 있었는데, 문제의 목적이 비교 횟수를 구하는 것이므로 만약 N이 1일 경우 답은 0이 되는 것과, 비교할 카드 묶음의 개수가 항상 최소여야 한다는 것입니다.

예를 들어, 10개인 카드 묶음이 5개(10, 10, 10, 10, 10) 주어진다면, (10+10) + (20+10) + (30+10) = 90이 아니라 (10+10)+(10+10)+(20+20) = 80이 되어야 합니다.

따라서, 카드 묶음을 합치기 전에 매번 개수가 가장 적은 카드 묶음을 골라야 하므로, Min Heap 기반의 우선순위 큐를 적용하였고, 합쳐서 하나로 만든 카드 묶음을 다시 우선순위 큐에 집어넣는 식으로 비교 횟수가 항상 최소가 되도록 하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    priority_queue<int, vector<int>, greater<int>> pq;
 
    int inputValue = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> inputValue;
        pq.push(inputValue);
    }
 
    int minCompareCount = 0;
    int compareCountA = 0;
    int compareCountB = 0;
    for (int i = 0; i < N - 1; i++)
    {
        compareCountA = pq.top();
        pq.pop();
        compareCountB = pq.top();
        pq.pop();
 
        pq.push(compareCountA + compareCountB);
        minCompareCount += compareCountA + compareCountB;
    }
 
    cout << minCompareCount;
 
    return 0;
}

---

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
N = int(input())
hq = []
minCompareCount = 0
 
for _ in range(N):
    heapq.heappush(hq, int(input()))
 
for _ in range(N - 1):
    compareCountA = heapq.heappop(hq)
    compareCountB = heapq.heappop(hq)
 
    heapq.heappush(hq, compareCountA + compareCountB)
    minCompareCount += compareCountA + compareCountB
    
print(minCompareCount)

---