99클럽 코테 스터디 24일차 TIL + 힙(C++)

문제

[백준] 1417번: 국회의원 선거

https://www.acmicpc.net/problem/1417

 

코드 1 - 우선순위 큐 사용 X

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> v;  // 득표수를 저장하는 배열
    int ans = 0;    // 매수한 사람 수

    while (N--) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    // 후보가 1명인 경우 0을 출력하고 종료
    if (v.size() == 1) {
        cout << 0 << '\n';
        return 0;
    }

    int dasom = v[0];  // 다솜이의 득표수

        while (1) {
            // 다솜이를 제외한 득표수들 중 최댓값의 인덱스
            int max_idx = max_element(v.begin() + 1, v.end()) - v.begin();

            // 다솜이의 득표수가 가장 커지면 종료
            if (dasom > v[max_idx])
                break;

            v[max_idx]--;  // 최대 득표수를 1 감소시킴
            dasom++;       // 다솜이의 득표수를 1 증가시킴
            ans++;         // 매수한 사람 수를 1 증가시킴
        }

    cout << ans;

    return 0;
}

 

풀이

반복문을 돌면서 다솜이를 제외한 득표수들 중 최댓값을 구해, 최댓값을 1 감소시키고 다솜이의 득표수를 1 증가시킨다. 이때마다 다솜이가 매수한 사람의 수(ans)도 함께 1 증가시킨다.

다솜이의 득표수가 전체 득표수 중 가장 커지면 반복문을 탈출하고 매수한 사람 수(ans)를 출력하고 종료한다.

이때, 후보가 다솜이 1명밖에 없는 경우에는 0을 출력하고 종료하도록 한다.

 

코드 2- 우선순위 큐 사용

#include <bits/stdc++.h>
using namespace std;

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

    priority_queue<int> pq;
    int dasom = 0;
    int ans = 0;

    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        
        if (i == 0)
            dasom = x;  // 다솜이의 득표수는 따로 저장
        else
            pq.push(x); // 나머지 후보들의 득표수는 우선순위 큐에 삽입
    }

    while (!pq.empty()) {
        int max_vote = pq.top();
        pq.pop();

        // 다솜이의 득표수가 가장 크면 종료
        if (dasom > max_vote)
            break;

        pq.push(max_vote - 1);
        dasom++; 
        ans++;
    }

    cout << ans;

    return 0;
}

 

첫번째 코드를 제출하고 나서야 이 문제를 우선순위 큐(힙)로도 풀 수 있다는 걸 알게 됐다.

priority_queue<int> pq; 와 같이 우선순위 큐를 생성하면 큐 안에서 원소가 큰 순서대로 자동 정렬되므로,

매번 max_element를 호출해 최댓값을 찾지 않아도 pq.top()으로 큐의 원소들 중 최댓값을 구할 수 있다!