ACM 10142, Australian Voting

http://acm.uva.es/p/v101/10142.html  

생 소한 호주식 투표 제도 덕에 문제가 눈에 잘 들어오지 않는다는 점을 제외하고는 그리 어려울 것 없는 문제다. 나는 deque을 사용하여 문제를 해결했다. deque은 가장 앞/뒤에 있는 원소를 제거/삽입할 수 있다. 삽입은 push_back ()으로 넣고, 참조는 front ()하여 가장 높은 우선순위의 투표자를 가려냈다. 가장 앞에 최소로 표를 획득한 자가 있을 경우는 pop_front () 하여 제거했다. 덕분에 알고리즘은 쉽게 구현되었다.

 

1136560873_Australian Voting3.cpp

1136560873_input.txt

1136560873_output.txt

 

그러나... 이번 문제는 나의 시간복잡도 측정 능력이 얼마나 조악한지 깨닫게 해주었다. 일단 제거하는데 많은 시간이 소요되었다. 그도 그럴 것이 투표는 최대 20명에 대한 투표가 1000건이 들어오니 말이다.

 

더욱 문제는 최소 투표수 획득으로 탈락된 후보자를 일거에 투표지에서 제거하기 위해 모든 덱을 순회했다는 점이다. 이것 때문에 계속해서 시간초과가 발생했는데, 어서 풀어야겠다는 욕심 탓인지 잘 보이지 않았다. 엎친데 덮친 격으로 http://www.programming-challenges.com 에서는 solved 되었다. 덕택에 남탓(acm 서버)만 하고 소스 검토를 게을리했다...  많은 점을 뒤돌아보게 하는 문제였다.