검색결과 리스트
글
호주식 투표법(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순위로 선택한것만 집계, 한 후보가 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점을 받는다는 식이 아님을 기억하자!
말이 조금 어렵게 나와있다. 입력케이스는 현재 개표(?)중인 선거를 나타낸다는 것과 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 |
