문제
https://www.acmicpc.net/problem/4419
문제해설
투표를 통해 후보를 뽑는다.
다만 과정이 좀.. 정말 호주에서는 이렇게 하는지 궁금하다.
투표용지에는 후보별로 선호도가 적혀있다.
우선 가장 선호도가 높은 후보가 1표씩을 받는다.
만약 표를 가장 많이 받은 사람이 과반수의 표를 받았다면 그 사람이 당선된다.
하지만 과반이 안된다면
가장 적은 표를 받은 후보를 탈락시키고
그 후보에게 준 표는 그 다음으로 선호도가 높은 후보에게 투표한다.
그렇게 누군가 당선이 될 때까지 반복한다.
주의할 점은 모든 후보가 동일한 표를 받았다면
모든 후보를 출력해줘야 하고
후보를 탈락시킬 때 한명이 아닌 여러명이 탈락할 수 있다는 것이다.
문제풀이
지금것 풀어본 구현문제 중 가장 짜증났었다.
왜냐하면 이상한 부분에서 런타임 에러가 계속 났기 때문이다.
eof를 처리 할 때 while (!cin.eof())을 써서 6번이나 틀렸다…
아무튼 딱히 풀이가 존재하지 않는다.
그냥 구현이다 좀 복잡한
3개의 배열을 사용했다.
우선 이름을 저장한 배열,
후보의 표와 고유 번호를 저장한 배열,
선호도가 적힌 표를 저장한 배열
표를 저장한 배열은 벡터안에다 큐를 넣어서 만들었다.
나는 탈락한 후보를 -1로 처리하고
다시 투표를 할 때 -1의 후보에게 표를 주려고 하면
-1의 후보가 아닐 때까지 pop연산을 해주었다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
typedef pair<int, int>P;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
vector<string>name;
vector<P>arr;
string a;
getline(cin, a);
for (int i = 0; i < n; i++) {
string x;
getline(cin, x);
name.push_back(x);
arr.push_back({ 0,i });
}
int cnt = 0;
vector<queue<int>>score(1001);
int x;
while (cin >> x) {
x--;
score[cnt].push(x);
for (int i = 1; i < n; i++) {
int x; cin >> x; x--;
score[cnt].push(x);
}
cnt++;
}
while (true) {
for (int i = 0; i < cnt; i++) {
while (arr[score[i].front()].first == -1) {
score[i].pop();
}
arr[score[i].front()].first++;
}
int maxx = 0;
int minn = 999999999;
for (int i = 0; i < n; i++) {
if (maxx < arr[i].first)
maxx = arr[i].first;
if (minn > arr[i].first && arr[i].first != -1)
minn = arr[i].first;
}
if (maxx * 2 > cnt || maxx == minn) {
for (int i = 0; i < n; i++) {
if (arr[i].first == maxx)
cout << name[arr[i].second] << "\n";
}
return 0;
}
for (int i = 0; i < n; i++) {
if (arr[i].first == minn) {
arr[i].first = -1;
}
if (arr[i].first == -1) continue;
arr[i].first = 0;
}
}
return 0;
}