호주식 투표법(Australian Voting)

Programming/Algorithm 2010. 8. 27. 22:02
호주식 투표 제도에서는 투표권자가 모든 후보에 대해 선호도 순으로 순위를 매긴다.
처음에는 1순위로 선택한것만 집계, 한 후보가 50 % 이상 득표시 바로 선출된다. 하지만 50% 이상 득표한 후보가 없으면 가장 적은표를 받은 후보(둘 이상 될 수도)가 우선 탈락된다. 그리고 이렇게 탈락된 후보를 1순위로 찍었던 표를 다시 집계, 아직 탈락되지 않은 후보가운데 가장 높은 선호도를 얻는후보가 그 표를 얻는다. 이런 식으로 가장 약한 후보들을 탈락시키면서 다음 순위의 탈락하지 않은 후보에게 표를 주는 과정을 50% 이상을 얻는 후보가 나오거나 탈락되지 않은 모든 후보가 동률이 될 때까지 반복한다.

입력

입력 케이스의 개수를 나타내는 양의 정수 한 개가 들어있는 행으로 시작되며 그 줄에는 그 숫자밖에 입력되지 않는다.
그 뒤에는 빈줄이 하나 들어가고 서로 다른 입력 케이스 사이에는 두개의 빈줄이 입력된다.
각 케이스의 첫번째 줄에는 후보 수를 나타내는 20 이하의 정수 n이 입력된다. 그 밑으로 n개의 줄에 걸쳐서 후보의 이름이 순서대로 입력되며 각 후보의 이름은 80글자 이하로, 출력가능한 문자로 구성된다.
그 뒤에는 최대 1,000줄이 입력될 수 있는데, 각 줄에는 투표 내역이 입력된다. 각 투표 내역에는 어떤 순서로 1부터 n까지의 수가 입력된다. 첫번째 숫자는 1순위로 찍은 후보의 번호, 두번째 숫자는 2순위로 찍은 후보의 번호, 이런식으로 숫자가 입력된다.

출력

각 테스트 케이스에 대해 당선된 후보의 이름 한줄, 또는 동률을 이룬 후보들의 이름이 들어있는 여러 줄을 출력한다.
두 개 이상의 테스트 케이스가 있는 경우 각 결과는 한 개의 빈 줄로 구분한다


입력 예                                            출력 예

1                                                  John Doe
3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

주의해야 할 점
말이 조금 어렵게 나와있다. 입력케이스는 현재 개표(?)중인 선거를 나타낸다는 것과 1,000줄 입력중에 중지하는 키워드는 "두개의 빈줄"임을 확인하자. 두 개의 빈줄은 개인적으로 아주 조잡하게.. gets함수를 이용하였다.
또한 같이 푼 동료가 대단히 헷갈려한 부분인데, 위의 입력예에서 첫번째 사람이 가장 선호하는 후보자가 1번 후보자(john)이며, 그다음이 2번째, 3번째 임을 기억하자. john이 1점을 받고 jane이 2점을 받는다는 식이 아님을 기억하자!





 


'Programming > Algorithm' 카테고리의 다른 글

ACM-ICPC 2009년도 기출 _ Candy War  (0) 2010.10.01
암호 깨기 (Crypt Kicker)  (0) 2010.09.30
동맹 휴업 (Hartal)  (0) 2010.09.03
포커 패(Poker Hands)  (0) 2010.09.01
유쾌한 점퍼(Jolly Jumpers)  (0) 2010.08.31