[백준] - Australian Voting (호주식 투표법) 4419

---

https://www.acmicpc.net/problem/4419

4419번: Australian Voting

---

처음에는 해석하기 귀찮아서 번역기 돌렸는데 도통 뭔 소리를 하는건지 몰라서,

문제 번역본이 있나 찾아 봤는데 맞힌 사람이 몇명 없어서 그런가 해당 문제 관련 글은 찾지 못했다.

 

그래서 눈물을 머금고 원문 해석을 해봤는데 호주식 투표 방법에 관해 써져 있었다.

 

호주식 투표제도는 우리나라와 다르게 모든 선거 후보에 대해서 우선 순위별로 나열하는 방식이다.

• 후보자 중 과반수 이상 1순위 표를 받은 후보자가 있으면 당선됩니다.
• 만약 1순위 표를 가장 많이 받은 후보자의 득표율이 과반수 미만일때는 1순위 표가 가장 적은 후보자가 탈락된다.
• 탈락된 후보를 1순위로 찍었던 표를 가지고 다음으로 높은 순위를 가지는 후보에게 표를 주는 방식이다.
• 이렇게 1순위 표가 과반 수 이상 받은 후보자가 있을때 까지 반복한다.

 예를 들어) 후보자가 (1번 홍길동) (2번 박세영) (3번 김길동)이 있으면 아래와 같이 투표한다.

                  ->  1순위 John,    2순위 Jane,     3순위 Sirhan

 

아래 예제를 보면 John 2표, Jane 2표, Sirhan 1표를 받았고 최다 득표수가 2/5이므로 40%이다.

최다 득표수가 과반수 (50%)를 넘지 못했기 때문에 Sirhan 후보는 탈락되고 Sirhan 후보를 1등으로

찍은 표를 가지고 다시 집계를 한다.

 

아래 예제에서는 Sirhan 후보를 1등으로 찍은 표가 (1순위: Sirhan, 2순위: John, 3순위: Jane) 하나이고,

위 투표지를 보면 다음 순위는(2위) John이다.

이렇게 되면 John에게 표가 넘어가고 John은 3표 Jane은 2표로 John이 최다 득표자가 된다.

John의 득표율이 60 %이기 때문에 John이 당선이 된다. 

 

여기서 주의할 점은 탈락자가 한명 이상일 수 있고 당선자 또한 한명 이상일 수 있다. 

 

---

첫 제출 당시 틀렸습니다가 나와서 적잖아 당황했다.

어디서 틀렸는지 모르겠어서 인터넷을 참고 하고자 했지만 아무리 뒤져봐도 해당 문제에 관해 글을 쓴 사람을

확인할 수 없었다. 그래서 테스트 케이스를 찾아서 원인을 찾아보자 결심을 먹었고 고생 끝에 아래 사이트에서

테스트 데이터를 확인할 수 있었다. 

 

https://uwaterloo.ca/international-collegiate-programming-contest/past-local-contest-results

Past Local Contest Results | International Collegiate Programming Contest

---

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {

    public static HashMap<String, Integer> candidates = new HashMap<>();
    public static int n;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = "";

        n = Integer.parseInt(br.readLine());
        ArrayList<String> nameList = new ArrayList<>();

        // 17 ~ 40 initialize
        for(int i=0; i<n; i++) {
            String name = br.readLine();
            candidates.put(name, 0);
            nameList.add(name);
        }

        int votes[][] = new int[1000][1000];

        int idx = 0;
        while((input = br.readLine())!= null){
            StringTokenizer st = new StringTokenizer(input);

            for(int i=0; i<n; i++)
                votes[idx][i] = Integer.parseInt(st.nextToken());

            idx ++;

        }

        for(int i=0; i<idx; i++){
            String name = nameList.get(votes[i][0]-1);
            candidates.put(name, candidates.getOrDefault(name, 0)+1);
        }

        while(true){
            // 44 ~ 45 투표순으로 후보자 오름차순 정렬
            List<Map.Entry<String, Integer>> entryList = new LinkedList<>(candidates.entrySet());
            entryList.sort(Map.Entry.comparingByValue());

            // 최다 득표수의 백분율
            double max = (entryList.get(entryList.size()-1).getValue() / (double) idx) * 100;

            int minValue = entryList.get(0).getValue();
            int maxValue = entryList.get(entryList.size()-1).getValue();

            // 최다 득표수가 과반 수 이거나 최대 값과 최소 값이 같으면 후보자들을 출력하고 종료 54 ~ 69
            if(max > 50 || minValue == maxValue) {
                Stack<String> st = new Stack<>();

                // 최대 득표 후보가 여러명 있을 수 있으므로 모두 출력
                for(int i=entryList.size()-1; i>=0; i--){
                    st.push(entryList.get(i).getKey());

                    if(i == 0 || entryList.get(i).getValue() != entryList.get(i-1).getValue()) break;
                }

                // entryList를 맨 끝에서 부터 탐색 했기 때문에 거꾸로 다시 출력
                while(!st.isEmpty())
                    System.out.println(st.pop());

                break;
            }

            // 최소 득표 후보자들을 제거 (최소 득표 후보자들이 여러명 있을 수 있으므로 모두 제거) (72 ~ 83)
            for(int i=0; i<entryList.size()-1; i++, idx--){
                String name = entryList.get(i).getKey();
                int index = nameList.indexOf(name);

                entryList.remove(0);
                candidates.remove(name);

                // 최소 득표자 제거 후 다음 순위 후보자에게 표를 넘겨줌
                findNextVote(votes, index+1, nameList, minValue);

                if(minValue != entryList.get(0).getValue()) break;
            }
        }

    }

    public static void findNextVote(int [][] votes, int idx, ArrayList<String> nameList, int minValue){

        for(int i=0; i<votes.length; i++){

            if(votes[i][0] != idx) continue;

            for(int j=1; j<n; j++){
                String name = nameList.get(votes[i][j] - 1);

                if(candidates.containsKey(name)){
                    if(minValue < candidates.get(name))
                        candidates.put(name, candidates.get(name) + 1);
                    break;
                }
            }
        }
    }

}