문제 8, 호주식 투표법 (Australian Voting)

PC/UVa ID : 110108/10142

사설

개인적으로 책에 적혀있는 문제가 이해가 되지 않았다, 도데체 무슨 말을 하는지 몰라, 친구(박형준)과 토론을 하며 문제를 생각했고, 형준이가 문제에 대해서 이해하여, 여기에 정리하게 된다.

답지를 보고, 형준이가 말한 문제가 올바른지 검증을 했으므로, 이 문제가 100% 정확하다. 책의 문제가 이해가 되지 않아, 검색하다 이 블로그를 찾게 된 사람들에게 도움이 되었으면 한다.

개요

호주식 투표 제도를 구현하는 문제입니다. 호주식 투표 제도는 다음과 같은 알고리즘에 따라 후보자가 당선됩니다.

1. 투표권자는 모든 후보자에게 순위를 메겨 투표를 합니다.
   
2. 이때 1순위 후보자만을 집계하여, 과반수 이상 표를 얻은 사람이 있다면, 당선을 시킵니다.
   
3. 만약 당선자가 없다면, 제일 표를 못 받은 후보자(복수 가능)를 탈락 시킵니다.
   
4. 탈락된 후보자를 최 상위 순위로 찍은 투표용지들 중 그 다음 순위자로 표기된 자가 있다면, 그 순위자에게 표를 줍니다.
   
5. 그리고 다시 집계하여, 과반수 이상 표를 얻은 사람이 있다면, 당선을 시키고 당선된 사람이 없다면, 3번의 처리과정을 반복하게 됩니다.
   

입력

1. 처리하고자 하는 투표 케이스(대통령 선거, 학급반장선거 등을 동시에 진행할 경우, 2 케이스 이다.) 의 갯수를 의미하는 양의 정수를 1개 입력 받는다.
   
2. 그 다음 빈줄이 하나 들어 간다.
   
3. 그리고 투표 케이스 중 첫번째 케이스의 후보자를 수를 양의 정수 1개로 입력받는다. - 예외 : 20명 이하
   
4. 그리고 그 후보자 수 만큼 이름을 입력 받는다. - 예외 : 80자 이하
   
5. 그리고 이름 출력
   
6. 그리고 투표용지를 받는다 - 예외 : 장수는 1000장 이하로 받는다.
   
7. 그리고 빈줄을 입력하면(그냥 엔터만) 투표 결과를 출력한다.
   

출력

1. 당선된 후보자가 있다면 이름을 출력한다.
   
2. 이때 다른 케이스의 투표도 있다면, 빈줄 한개를 출력하고, 다시 입력받고 반복한다.

입력과 출력의 예

http://books.google.co.kr/books?id=lcnSCDcDocMC&pg=PA25&lpg=PA25&dq=110108+10142&source=bl&ots=tMLKzbDL8O&sig=emx4BRw-AM1aFvc0l6hS18IwRJw&hl=ko&ei=gwvtSvD4BZqW6wOJ_tnvCw&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAgQ6AEwAA#v=onepage&q=110108%2010142&f=false

풀이

-- 투표 인원 제한 LIMIT_NUM_OF_VOTE = 1000 -- 후보자 제한 LIMIT_NUM_OF_CANDIDATE = 20 -- 투표용지에서 투가 최고의 후보자인지 찾는 함수이다. -- 투표용지를 받고, 총 투표자를 받는다. function who_is_number_one( the_votes ) -- 집계된 투표를 기록하기 위한 테이블 total_of_candidate = {} -- 모든 투표용지를 훑은다. for i, vote in ipairs( the_votes ) do -- 투표지에 살아 있는 후보자가 있을 경우 if 0 ~= #vote then -- 그 투표지의 첫번째 후보자만 뽑아 집계를 한다. if nil == total_of_candidate[ vote[1] ] then total_of_candidate[ vote[1] ] = 1; else total_of_candidate[ vote[1] ] = total_of_candidate[ vote[1] ] + 1; end end end max_total_num_of_vote = 0 index_of_best_candidate = 0 -- 가장 많은 표를 얻은 후보자의 인덱스를 찾고 for k, v in pairs( total_of_candidate ) do if v >= max_total_num_of_vote then max_total_num_of_vote = v index_of_best_candidate = k end end -- 과반수 이상의 표를 얻었다면 리턴하고 끝냈다. if max_total_num_of_vote > (#the_votes / 2) then return index_of_best_candidate end -- 그렇지 않으면, 제일 적은 표를 얻은 후보자의 인덱스를 찾고 min_total_num_of_vote = max_total_num_of_vote index_of_worst_candidate = 0 for k, v in pairs( total_of_candidate ) do if v <= min_total_num_of_vote then max_total_num_of_vote = v index_of_worst_candidate = k end end -- 최하 표와 최고 표가 같다면, 더 이상 집계할 수 없으므로 -- 재투표를 하기 위해 종료 한다. if max_total_num_of_vote == min_total_num_of_vote then return 0 end -- 모든 투표용지에서 for i, vote in ipairs( the_votes ) do -- 최악의 후보자를 찾고 for i, index_of_candidate in ipairs( vote ) do if index_of_worst_candidate == index_of_candidate then -- 그 후보자를 지운다. table.remove( vote, i ) break end end end -- 그리고 한번 더 호출한다. return who_is_number_one( the_votes ) end function main() -- 투표 케이스를 입력받는다. vote_case_num = io.read() vote_case_num = tonumber( vote_case_num ) if nil == vote_case_num then print("error : The num of vote case is invalid!") return end print("") -- 투표 케이스 만큼 처리 하는 루프를 돈다. for i = 1, vote_case_num, 1 do -- 투표 후보자 수를 입력 받는다. candidate_num = io.read() candidate_num = tonumber( candidate_num ) -- 입력값이 숫자가 아니거나, 한계범위를 넘었다면 에러 출력 if nil == candidate_num or LIMIT_NUM_OF_CANDIDATE < candidate_num then print("error : The num of candidate is invalid!") return end candidate_name_pack = {} -- 후보자 이름 -- 모든 후보자의 이름을 입력 받는다. for i = 1, candidate_num, 1 do candidate_name_pack[#candidate_name_pack + 1] = io.read() end -- 투표용지를 받는다, 투표 용지에는 모든 투표자들에 -- 대한 순위를 메겨야 하며, 잘못 입력했을 경우, 무시한다. the_votes = {} -- 투표 용지 for i = 1, LIMIT_NUM_OF_CANDIDATE, 1 do vote_t = {} -- 투표용지를 문자열로 받는다. vote_str = io.read() -- 입력값이 공백일 경우, 투표용지를 다 받은것으로 설정함 if "" == vote_str then break end -- 용지에 숫자가 된 부분만 순서대로 받아와 투표용지(테이블형)에 밀어 넣는다. for candidate_index in string.gmatch( vote_str, "%d+" ) do vote_t[ #vote_t + 1] = tonumber( candidate_index ) end -- 준비가 다된 투표 용지를 토표용지함에 넣는다. the_votes[#the_votes +1] = vote_t end -- 이제 집계를 시작한다. number_one = who_is_number_one( the_votes ) print( candidate_name_pack[number_one] ) end end

예외적으로 최대 취득수와 최소 취득수가 같다면, 누구를 탈락 시킬지 정할 수 없기 때문에, 재투표를 하게 한다.이로서 챕터 1이 끝났다. 챕터 2, 자료 구조로 넘어간다.