[S5] 1417. 국회의원 선거

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

1417번: 국회의원 선거

문제는 쉽다.

우선순위 큐를 이용해서 해결하려하다 보니 처음 사용하는 함수, 라이브러리가 많아 글을 작성한다.

우선 문제 이해부터 해보자

왜 이 문제가 우선순위 큐를 사용해야 할까?

 

나는 살짝 머리는 덜 쓰지만, 시간은 오래걸리지 않는 방법을 사용했다.

1. 반복문을 통해 dasom과 후보 중 상위 1명의 투표를 한개씩 늘리고, 차감하도록 하였다.

2. 다솜이 상위 1명의 투표율보다 높으면 종료.

 

1, 2번을 보더라도 알 수 있다. 다솜을 제외한 후보들의 투표율 중 상위 1명의 투표율을 알아야 한다. 그리고, 그 투표율을 변경할 수 있어야 한다 이다. 상위 1명의 투표율만 알면 된다는 것이다. 그렇기 때문에 나는 우선순위 큐를 사용하려 한다. 우선순위 큐가 무엇이냐. 다음 글을 참고하자. 나는 다양한 방법을 사용하였다.

 

1. 벡터를 이용하여 make_heap함수를 사용하여 heap형태로 만들고 그것을 이용하는 것.

2. 우선순위 큐 자료구조를 사용하여 pop과 push를 이용하는 것.

이 두 가지의 방법은 약간의 차이가 있다. 하지만 효율이 무엇이 좋은지는 나도 잘 모르겠다.

이것에 대한 설명은 나중에 하도록 하겠다.

3. 직접 heapify구현이다.

나는 우선순위 큐를 C++에서 지원해주는 줄 모르고 직접 heapify를 만들어 코드를 처음에 작성하였다. 나중에 있다는 사실을 알고 글을 작성하는 중이다.

 

우선 priority_queue에 대해 알아보자. 이에 대한 설명은 queue와 관련한 글에 있다.

https://jhcard.tistory.com/69

[C++] queue 라이브러리

또한 algorithm 라이브러리를 활용해서 vector자료구조를 힙 형태로 변환시키는 방법도 있다. algorithm 라이브러리 관련 글을 참고 바란다.

https://jhcard.tistory.com/13

[C++] algorithm 라이브러리

 

이제 내가 작성한 코드를 1,2,3번 순서대로 보여주겠다.

1. priority_queue 사용

#include <cstdio>
#include <queue>

int main(void) {
	std::priority_queue<int> q;
	int N; scanf("%d", &N);
	int dasom; scanf("%d", &dasom);

	int score;
	for (int i = 1; i < N; i++) {
		scanf("%d", &score);
		q.push(score);
	}

	int count = 0;
	while (!q.empty() && dasom <= q.top()) {
		dasom++;
		q.push(q.top() - 1);
		q.pop();
		count++;
	}
	printf("%d", count);
}

 

2. make_heap 사용

#include <cstdio>
#include <vector>
#include <algorithm>

int main(void) {
	int N; scanf("%d", &N);
	int dasom; scanf("%d", &dasom);
	std::vector<int> v(N-1);

	int score;
	for (int i = 1; i < N; i++) scanf("%d", &v[i-1]); 
	std::make_heap(v.begin(), v.end());

	int count = 0;
	while (!v.empty() && dasom <= v.front()) {
		dasom++;
		v[0]--;
		if ((v.size() >= 2 && v[0] < v[1]) || (v.size() >= 3 && v[0] < v[2])) {
			std::pop_heap(v.begin(), v.end());
		}
		std::push_heap(v.begin(), v.end());
		count++;
	}
	printf("%d", count);
}

 

3. 직접 구현한 heapify 사용

#include <cstdio>

void swap(int heap[], int a, int b) {
    int tmp = heap[b];
    heap[b] = heap[a];
    heap[a] = tmp;
}

void heapify(int heap[], int loc, int num) {
    heap[loc] = num;

    while ((loc - 1) / 2 >= 0) {
        if (heap[loc] > heap[(loc - 1) / 2]) swap(heap, loc, (loc - 1) / 2);
        else break;
        loc = (loc - 1) / 2;
    }
}

int main(void) {
    int turn;
    scanf("%d", &turn);

    int dasom;
    int count = 0;
    scanf("%d", &dasom);

    int* heap = new int[turn - 1]();
    for (int i = 0; i < turn - 1; i++) {
        int num;
        scanf("%d", &num);
        heapify(heap, i, num);
    }

    while (dasom <= heap[0]) {
        dasom++;
        heap[0]--;
        count++;

        int index = 0;
        while (index * 2 + 1 < turn-1) {
            int maxIndex = index * 2 + 2 < turn-1 && (heap[index * 2 + 1] < heap[index * 2 + 2])
                ? index * 2 + 2 : index * 2 + 1;
               
            if (heap[index] < heap[maxIndex]) {
                swap(heap, index, maxIndex);
                index = maxIndex;
            }
            else break;
        }
    }
    printf("%d", count);
}