-
백준 1715번 카드 정렬하기: C++ 풀이Programming/PS 2024. 5. 1. 17:09
백준 1715 카드 정렬하기 문제의 C++ 해설입니다.
우선순위 큐(최소 힙)를 사용한 일반적인 풀이와 배열을 사용한 더 효율적인 풀이, 두 가지 방법을 설명합니다.
백준 13975 파일 합치기 3 와 유사한 문제입니다.기본 접근: 우선순위 큐 활용
비교 횟수 최소화 전략
제시문에서도 언급하듯, 카드 묶음을 고르는 순서에 따라 비교 횟수가 매우 달라진다.
카드를 합치며 묶음 크기가 누적으로 더해지기 때문이다.큰 값을 누적으로 더하는 것 보다, 작은 값을 누적으로 더하는 게 좋다.
따라서 비교 횟수 최소화를 위해 현재 카드 묶음 중 크기가 가장 작은 두 카드 묶음을 먼저 합쳐야 한다.우선순위 큐를 사용하는 이유와 시간 복잡도
카드를 저장하기 위해 일반적인 배열을 사용한다고 생각해보자.
배열을 정렬하면 크기가 가장 작은 두 묶음을 $O(1)$에 손쉽게 구할 수 있다. 가장 앞/뒤에 있는 원소 2개이다.
찾은 두 묶음을 합쳐 새로운 묶음을 만들어 준다. 재료가 된 두 원소를 배열에서 삭제하고, 새 묶음을 배열에 넣어줘야 한다.이때 새로운 묶음을 정렬에 맞는 위치에 삽입해야 한다.
정렬에 맞는 적절한 위치를 찾고, 삽입을 위해 배열 원소를 이동시켜야 한다.배열은 정렬된 상태이므로 이진 탐색을 사용하면 삽입 위치는 $O(logn)$에 찾을 수 있다.
삽입을 위해 원소를 이동하는 작업은 $O(n)$이 걸린다.
즉, 매 반복은 $O(n)$을 요구한다.우선순위 큐를 사용하면 배열처럼 간단하게 $O(1)$에 최솟값을 확인할 수 있으면서,
최솟값 2개 확인 및 삭제, 새 묶음 삽입 작업을 각 $O(logn)$으로 처리할 수 있다.따라서 우선순위 큐를 사용한다.
출력값 범위
누적합을 구하는 문제 특성 상, 최종 값이 int 범위를 벗어날 수 있다.
카드 묶음 최댓값은 1,000, 묶음 수는 최대 100,000 이다.
가능한 최대 비교 횟수는 대략 100,000 * 50,000 * 1000 = 5,000,000,000,000 정도 되겠다.int 범위를 벗어나므로 long을 써주자.
int로 해도 정답 처리가 되긴 한다.
코드 구현
#include <iostream> #include <queue> #define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr) using namespace std; int main() { FASTIO; priority_queue<long, vector<long>, greater<long>> pq; int num_cards; cin >> num_cards; while (num_cards--) { int card_size; cin >> card_size; pq.push(card_size); } long curr_sum; long total_sum = 0; while (pq.size() >= 2) { curr_sum = pq.top(); pq.pop(); curr_sum += pq.top(); pq.pop(); total_sum += curr_sum; pq.push(curr_sum); } cout << total_sum << '\n'; }- 루프 종료조건: 카드 묶음이 하나가 남을 때까지 진행함에 유의
개선된 접근: 정렬이 보장된 큐
우선순위 큐의 비효율성/한계
과연 우선순위 큐가 최선의 풀이가 맞을까?
힙으로 구현 된 우선순위 큐는 삽입/삭제 시마다 구조 유지에 $O(logn)$이 소요된다.
풀이를 보면 작업 한 번 당 삽입/삭제가 총 3번 일어난다. 삽입/삭제 시마다 힙 구조를 유지해야 하기에, 총 3번 정렬이 이루어진다.사실 힙 구조는 작업 전과 작업 후에만 유지되면 된다. 중간에 구조가 깨져도 별 상관이 없다.
이를테면 삭제 후, 삽입 이전에 자료가 어떻게 정렬 되어있는지는 크게 중요하지 않다.구조 정리를 필요한 시점에 한 번만 하도록 하거나, 최솟값 두개를 한 번에 가져올 수 있다면 더 효율적일 것이다.
이런저런 삽질을 해보다가, 다음을 발견했다.정렬 보장 특성을 이용한 최적화
문제 상황을 생각해보자. 최솟값 2개를 더해가며 새 카드 묶음을 만들기를 반복한다.
이때 N번째로 만든 묶음보다 N+1 번째로 만든 묶음의 크기가 당연하게도 항상 더 크다.
따라서 새로 만들어진 카드의 크기는 오름차순 정렬이 보장된다.처음부터 책상 위에 있었던 카드 배열을
desk_cards라고 하자.
그리고 빈 큐를 하나 만든다. 이름은mixed_queue로 하자.
이제부터 모든 새로운 묶음은mixed_queue에 넣어준다.일단
desk_cards를 정렬한다. $O(nlogn)$이 소요된다.
정렬을 마쳤으니 최솟값은 쉽게 찾을 수 있다. 둘을 더해 새 묶음을 만들어 준다.
새 묶음은mixed_queue에 넣어준다. 제일 뒤에 넣기만 하면 되니 삽입은 $O(1)$이다. 그래도 항상 정렬이 보장된다.이제부터 최솟값을 찾을 때마다
desc_cards와mixed_queue의 최솟값을 비교한다.
최솟값은desc_cards의 최소와mixed_queue의 최소 중 더 작은 값이 된다.desc_cards는 이미 정렬을 해놓았다. 최솟값은 가장 앞 원소이다. 최솟값을 삭제해도 정렬이 유지된다.mixed_queue도 마찬가지로 최솟값은 가장 앞 원소이며, 삭제해도 정렬이 유지된다. 합친 묶음을 다시 넣어도 정렬이 유지된다.최솟값 확인, 삭제, 삽입 모두 $O(1)$에 이루어진다.
기존 방법보다 훨씬 빠른 작업이 가능하다.개선된 코드 구현
#include <iostream> #include <climits> #include <vector> #include <queue> #include <algorithm> #define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr) using namespace std; int main() { FASTIO; int num_cards; cin >> num_cards; // dummy max value vector<long> cards(num_cards + 1); cards[0] = LONG_MAX; for (int i = 1; i <= num_cards; i++) { cin >> cards[i]; } sort(cards.begin(), cards.end(), greater<long>()); // Guarenteed to be sorted, no need to use priority queue queue<long> mixed_queue; mixed_queue.push(cards.back()); cards.pop_back(); long curr_sum; long total_sum = 0; num_cards--; // Merge n-1 times while (num_cards--) { // Choose 1st card stack if (mixed_queue.front() <= cards.back()) { curr_sum = mixed_queue.front(); mixed_queue.pop(); } else { curr_sum = cards.back(); cards.pop_back(); } // Choose 2nd card stack if (!mixed_queue.empty() && mixed_queue.front() <= cards.back()) { curr_sum += mixed_queue.front(); mixed_queue.pop(); } else { curr_sum += cards.back(); cards.pop_back(); } total_sum += curr_sum; mixed_queue.push(curr_sum); } cout << total_sum << '\n'; }