우리가 선거에서 주로 사용하는 형태의 투표는 한 표씩 피선거자에게 던짐으로써 그 표가 가장 많은 사람이 당선되는 형태를 따른다.

그런데 특히 정치와 같은 경우, 정치적인 색채가 비슷한 인물이 여럿 등장하면 비슷한 표밭에서 표가 오기 때문에 표가 갈리는 현상을 보인다.

따라서 오히려 객관적인 지지율이 낮은 사람이 당선될 가능성이 있다.

이와 같은 단점을 막기 위해 아래와 같은 투표를 생각하자.

선거권이 있는 각 유권자는 각 후보에 대한 선호도를 [1, N]의 순열로 나타낸다. 즉, 가장 선호하는 사람은 누구이고 그 다음으로 선호하는 사람은 누구이고 .. 와 같이 진행한다.

당선자를 결정하기 위해 아래의 단계를 반복한다.
- 과반 이상으로부터 선호도 1위인 후보가 있다면 그 후보가 당선이다.
- 당선이 결정되지 않았으면 가장 적은 유권자들로부터 선호도 1위로 표시된 후보는 투표에서 제외된다. 여럿 있다면 모두 제외된다.
- 유권자들의 선호도는 제외된 후보들을 고려하지 않았을 때의 순위로 다시 매긴다. 즉, 어떤 유권자에게 2위였던 후보가 제외되었다면 3위였던 후보가 2위, 4위였던 후보가 3위가 되는 식이다.
- 아무런 후보도 남지 않는다면 투표는 무효다.

유권자들의 투표 결과가 주어졌을 때 당선자가 누구인지 알아내어라.

선거 timer 1s memory 64MB

선거 1s 64MB