[BOJ 2817 - Java] 알프스식 투표 - 구현문제

728x90

문제정보

문제

전대프연(전국 대학생 프로그래밍 대회 동아리 연합)에서는 매년 프로그래밍 대회를 연다. 올해도 무사히 대회를 개최한 전대프연 회장 성진은 수고해준 스태프들에게 수고비를 주기로 하였다. 하지만 몇몇 스태프는 일을 열심히하지 않았기 때문에 성진은 일을 열심히 한 사람에게만 주기로했다. 하지만 일을 무진장 열심히 한 사람과 덜 열심히 한 사람에게 수고비를 똑같이 주는 것은 불공평하다.

고민을 한 성진은 수고비를 받을 사람을 선출하는 방식으로 ALPS(Allegro Leader Picking System) 을 사용하기로 결심했다. ALPS는 이름에서 보이듯이, 아주 유쾌하고 빠르게 사람들을 선별하는 방법이다.

우선 대회 참가자들은 "수고비를 받을 가치가 있는 스태프" 한 명을 선택해 투표를 한다. (참가자가 투표를 하지 않을 수도 있다.) 이 투표결과, 전체 대회 참가자의 5% 미만의 득표를 얻은 사람은 열심히 일을 하지 않은 스태프이므로 후보에서 제외해버린다. 이제 남은 스태프마다, 받은 득표수를 1로 나눈 값, 2로 나눈 값... 14로 나눈 값을 구한다. 이렇게 구한 14개의 실수가 그 스태프의 '점수'들이 된다.

이렇게 14 * (후보 스태프의 명수) 개의 실수를 가진 점수집합을 얻을 수 있다. 이 점수집합에서의 값에 따라 각 스태프들에게 14개의 칩을 나눠주는데, 집합 내에서 가장 큰 점수를 가진 후보 스태프에게 1개의 칩을 주고, 집합 내에서 두 번째로 점수가 큰 후보 스태프에게 1개의 칩을, ... 14번째로 점수가 큰 후보 스태프에게 1개의 칩을 준다. 최종적으로 스태프마다 득표수에 따라 칩의 개수가 다르게 지급될 것이다. 이것이 바로 ALPS식 투표이다. 성진은 스태프가 가진 칩의 개수에 비례해서 수고비를 지급하기로 했다. 신비롭게도, 점수집합에 있는 실수들은 항상 서로 다르도록 투표결과가 나온다고 한다.

우리는 각 스태프마다 몇개의 표를 얻었는지를 알고있다. 이 득표수를 토대로, ALPS식 투표를 수행하게 된 후, 각 스태프가 받을 칩의 개수를 구하는 프로그램을 작성하시오.

슈도 코드

임포트
메인메서드 생성
전체 참여자 N , 스태프 수 C
스태프와 스태프 투표수를 담는 배열 생성 staffs[26], vote[26]
스태프 수만큼 반복문 돌림
스태프 변수 target, 투표 수 vote생성, 참여가능한 staffCount 생성
만약 vote가 N*0.05를 넘는다면 staffts[target-’A’]에 true, vote[target-’A’]에 vote수 담기, staffCount++하기
Score클래스 생성, 유저의 idx와 score값을 갖고 있음
score[] 배열을 staffCount*14의 크기로 생성
26개의 참여자를 순회하며 true일경우 1~14의 점수집합을 생성하여 Score객체로 담기
각 점수를 내림차순으로 정렬(삽입 정렬)
정답을 출력할 배열 answer[] 배열을 26만큼 생성
score[]배열을 순회하며 위에서 14개의 값을 각각 answer[score[i].staffIdx]++
스태프가 참인 배열의 이름과 값을 출력

주요 규칙

반복되는 규칙은 없지만 내용속의 방식을 잘 읽고 구현해야함
아직도 왜 이런 방식으로 구하고 문제속에서 이 방식에 대한 설명이 제대로 되어있는지는 잘 모르겠음…

구현 코드

package simulation;

import java.util.Scanner;

public class 알프식투표_2817 {

    static class Score{
        double score;
        int staffIdx;
        Score(int staffIdx, double score) {
            this.staffIdx = staffIdx;
            this.score = score;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int total = sc.nextInt();
        int N = sc.nextInt();

        boolean[] staffs = new boolean[26];
        int[] voteCount = new int[26];
        int candidateCount =0;

        //커트라인 넘는 스태프 구하기
        double cutLine = total * 0.05;
        while(N-- >0){
            String target = sc.next();
            int vote = sc.nextInt();
            if (vote >= cutLine) {
                int index = target.charAt(0)-'A';
                staffs[index] = true;
                voteCount[index] = vote;
                candidateCount++;
            }
        }

        //각 스태프 점수 구하기
        Score[] scores = new Score[candidateCount*14];
        int scoreIndex = 0;
        for (int i = 0; i < 26; i++) {
            if(staffs[i]){
                for (int j = 1; j <=14; j++) {
                    scores[scoreIndex++] = new Score(i, (double) voteCount[i]/j);
                }
            }
        }

        //3. 점수 내림차순
        sortScoresDescendingOrder(scores);

        int[] ans = new int[26];
        for (int i = 0; i < 14; i++)
            ans[scores[i].staffIdx]++;

        // 4. 스태프 이름에 대해 사전순으로 후보 스태프와 받은 칩의 수를 출력한다.
        for (int i = 0; i < 26; i++) {
            if (staffs[i])
                System.out.println((char)(i + 'A') + " " + ans[i]);
        }

    }

    private static void sortScoresDescendingOrder(Score[] scores) {
        for (int i = 0; i < scores.length; i++) {
            for (int j = 0; j < i; j++) {
                if (scores[i].score > scores[j].score) {
                    Score temp = scores[i];
                    for (int k = i; k >j; k--) {
                        scores[k] = scores[k-1];
                    }
                    scores[j] = temp;
                }
            }
        }
    }
}