백준 2817

 

문제

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

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

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

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

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

입력

첫 번째 줄에는 전대프연 대회에 참가한 참가자들의 수 X( 1 ≤ X ≤ 2,500,000) 이 주어진다. 두 번째 줄에는 전대프연에 참가한 스태프의 수 N (0 ≤ N ≤ 10) 이 주어진다.

다음 N개의 줄에 걸쳐 각 스태프의 정보 -스태프의 이름(항상 대문자 알파벳이다.)과 그 스태프가 받은 득표수- 가 공백을 사이에 두고 주어진다.

출력

득표율이 전체의 5% 이상인 스태프에 대해, 스태프의 이름과 그 스태프가 받은 칩의 개수를 한줄에 하나씩 출력한다. 출력하는 순서는 스태프 이름의 사전순이여야한다.

 

 

내 풀이..

 

답은 맞았지만 굉장히 비효율적인 것 같았다

조건인 5퍼를 넘는 사람들과 해당하는 득표수를 ArrayList에 담아서 각각 1~14 로 나눈 값을 담을 n*14 크기의 배열에 담고 정렬한다음 거꾸로 가져왔다. 문제에서는 사전순으로 정렬이 된 상태를 바랬기에 treeMap에 넣었다가 빼서 사전순으로 정렬해서 답을 구했다

 

public class Main {

    public static void solution(char[][] arr, String s)  {

    }

    public static void main(String[] args) throws IOException {

        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int n = in.nextInt();

        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<Character> name = new ArrayList<>();

        for (int i = 0; i < n; i++){
            char a = in.next().charAt(0);
            int tmp = in.nextInt();

            if ((float)tmp / x > 0.05){
                arr.add(tmp);
                name.add(a);
            }
        }

        // 이름, 초기 투표수를 가진 배열리스트 2개

        int[] votes = new int[14 *  arr.size()];
        for (int i = 0; i < arr.size(); i++){
            int tmp = i * 14;
            for (int j = 1; j <= 14; j++ ){
                votes[tmp] = arr.get(i) / j;
                tmp++;
            }
        }

        Arrays.sort(votes);

        //정렬된 배열의 뒤에 14개, 큰것부터 가져오기
        int[] res = new int[arr.size()];
        for (int i = votes.length-1; i > votes.length-14-1; i--){
            for (int j = 0; j < arr.size(); j++){
                for (int k = 1; k <= 14; k++){
                    if (arr.get(j) / k == votes[i]){
                        res[j] += 1;
                        break;
                    }
                }
            }
        }


        Map<Character, Integer> map = new TreeMap<>();

        for (int i = 0; i < arr.size(); i++){
            map.put(name.get(i),res[i]);
        }

        for (Character nKey : map.keySet()) {
            System.out.println(nKey + " " + map.get(nKey));
        }

    }
}