프로그래밍/알고리즘 PS

[C++] BOJ 1417번: 국회의원 선거

코딩 제이티 2024. 4. 12. 19:59

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다.

 

문제의 난이도는 실버 5으로, 우선 순위 큐를 활용해 푸는 것을 권장받은 문제이다.

문제 링크

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

문제 분석

다솜이가 국회 의원에 당선되도록 하기 위해 다른 사람에게 간 득표를 자신, 기호 1번에게 오도록 사람들을 매수하는 최소 횟수를 구하는 문제이다. 예를 들어 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표라고 한다면, 다솜이는 2번 후보를 찍으려고 하던 사람 1명과, 3번 후보를 찍으려고 하던 사람 1명을 돈으로 매수하면 기호 1번이 7표, 기호 2번이 6표, 기호 3번이 6표이므로 국회 의원에 당선된다.

자료 구조

1. 우선순위 큐 (Priority Queue)

 우리가 알고 있는 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO형 자료구조이다. 이와 달리, 우선순위 큐는 큐에 insert한 순서와 관계없이 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 우선 순위는 보통 최대 힙, 최소 힙과 같이 힙 자료구조를 통해 구현할 수 있다.

 

2. 힙 (Heap)

 Heap 자료구조는 데이터를 정렬하여 내보내고 싶을 때 사용하기 위해 고안된 완전 이진 트리이다. 이진 탐색 트리와 달리 중복되는 값이 들어오는 것 또한 허용되며, 부모 노드와 자식 노드 사이의 대소 관계가 존재한다. 하지만 힙 노드의 값이 모두 정렬된 것은 아니며, 부모와 자식 사이에만 정렬되어 있다.

 

 Heap은 대표적으로 부모 노드의 값이 자식 노드의 값보다 크거나 같은 최대 힙과 부모 노드의 값이 자식 노드의 값보다 작거나 같은 최소 힙 2종류가 존재한다.

 

 Heap의 강점은 배열이나 연결리스트에 비해 삽입과 삭제의 평균 시간 복잡도가 작은 편에 속한다. 배열이나 연결리스트는 삽입에 O(N)의 시간이 걸리지만 Heap은 완전 이진 트리이므로 O(logN)의 시간이 걸린다.

 

 우선순위 큐를 구현할 때에 다른 자료 구조를 사용해 구현하는 것도 가능하지만 Heap을 주로 사용하는 이유도 낮은 시간 복잡도에 있다.

문제 풀이

 이 문제의 핵심 키워드는 '다솜이는 기호 1번', '다른 모든 사람의 득표 수 보다 많은 득표수를 가지도록 하기'이다.

 

 다솜이가 다른 사람들보다 많은 득표수를 가졌는지 알 수 있는 방법 중 하나는, 가장 큰 득표수를 가진 사람보다 다솜이가 더 많은 득표를 받았는지 확인하는 것이다. 이 원리를 우선순위 큐를 이용하면 구현할 수 있다.

 

 C++에서는 queue 헤더 파일 내에 priority_queue 타입이 구현되어 있어 해당 헤더 파일을 불러와 사용하면 된다. 단 priority_queue는 기본적으로 최대 힙으로 객체가 생성되므로 만약 최소 힙과 같이 정렬되는 방식이 다르게 구현되어야 한다면 추가적인 코드 작성이 필요하다. 해당 문제에서는 최대 힙이 필요하므로 그대로 사용하면 된다.

 

 처음에 문제를 풀 때에는 기호 1번부터 기호 N번까지 모두 입력을 받아 우선순위 큐에 넣어서 푸는 방식으로 구현하려다 어려움을 겪었다. 그러나 다솜이가 기호 1번으로 고정되어 있으므로, 기호 N번까지 입력을 받을 때에 첫 번째 입력은 다솜이란 변수에 값을 따로 저장하고, 다솜이를 제외한 나머지 입력만 우선순위 큐에 넣어서 문제를 풀면 된다는 것을 알게 되었다. 이를 코드로 표현하면 다음과 같다.

int N;
int dasom;

priority_queue<int> pq;

cin >> N;
cin >> dasom;

for (int i = 1; i < N; i++)
{
    int vote;
    cin >> vote;
    pq.push(vote);
}

 

 이 때, 우선순위 큐는 pq라는 변수명을 갖도록 구현하였다. 위와 같이 코드를 작성하면 기호 1번에 대한 투표 수는 dasom 변수에 담기고 기호 2번부터 기호 N번까지의 투표수는 우선순위 큐에 담기게 된다.

 

 그 다음 코드로 우선순위 큐에서 가장 큰 값보다 다솜이 더 큰 값이 될 때까지 다솜이 다른 사람의 표를 매수하는 과정을 코드로 표현하면 다음과 같다.

int cnt = 0;

while (!pq.empty() && dasom <= pq.top())
{
    int max_value = pq.top();
    pq.pop();
    cnt++;
    dasom++;
    max_value--;
    pq.push(max_value);
}

 다음 코드에 대해 설명하며 다음과 같다. 

  1. 우선순위 큐에서 가장 큰 값을 읽는다. 해당 값이 다솜보다 작거나 같은 득표수라면 아래 과정을 거친다.
  2. 우선순위 큐에서 가장 큰 값을 꺼낸다. 이 값을 max_value라고 하였을 때, 다솜의 투표 수를 1 증가 시키고 우선순위 큐에서 꺼낸 값의 투표 수 max_value를 1 감소시킨다. 해당 부분이 문제에서 주어진 매수를 표현한 로직이다. 그리고 매수 횟수를 표현하는 변수 cnt의 값을 1 증가시킨다.
  3. 우선순위 큐에 max_value를 다시 삽입한다.
  4. 다솜이 가장 큰 득표수가 되면 반복문을 종료한다. 그렇지 않을 경우 위 과정을 반복한다.

 마지막으로 매수 횟수 cnt를 출력한다.

cout << cnt << '\n';

전체 코드

#include <iostream>
#include <queue>

using namespace std;

int N;
int dasom;

priority_queue<int> pq;
int cnt;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    cin >> dasom;

    for (int i = 1; i < N; i++)
    {
        int vote;
        cin >> vote;
        pq.push(vote);
    }

    while (!pq.empty() && dasom <= pq.top())
    {
        int max_value = pq.top();
        pq.pop();
        cnt++;
        dasom++;
        max_value--;
        pq.push(max_value);
    }

    cout << cnt << '\n';

    return 0;
}

 

저작자표시 (새창열림)