[240220] 알고리즘 리부트 12일차 - 백준 2817 자바

[Part1-Chapter04-Clip09]

- 백준 2817 ALPS식 투표

 

 

 

우선순위 큐나 set을 써야하나라는 고민이 들었던 문제였다. 아직 강의 순으로는 해당 자료구조를 배우지 않아서 최대한 배열을 사용하려고 했고 하지만 시간 복잡도를 고려했을 때 가장 높은 점수 순으로 칩을 부여하기 위해서는 적어도 리스트에 담아 정렬할 수밖에 없다는 생각이 들었다. 참가자들의 수가 250만이지만 스태프 수는 10명으로 제한되어 있고 나누는 값도 최대 14까지 적은 수가 반복문을 여러번 돌아도 시간 초과는 나지 않을 것 같았다. 또 칩을 부여하는 과정에서는 내림차순으로 정렬된 수를 각 스태프의 기본 점수로 나누었을 때 나머지가 0.0이면 칩을 부여하는 방식으로 처리했었는데 왜인지 찾을 수 없는 경우가 있어 모든 점수를 반복문으로 순회하면서 부여하는 방식으로 구현했다. 

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int staff = sc.nextInt();

        float[][] votes = new float[26][16];

        // 0열 = 총 득표 수
        // 15열 = 받은 칩 수

        for (int i = 0; i < staff; i++) {
            char staffName = sc.next().charAt(0);
            int votesNum = sc.nextInt();

            if (votesNum >= x * 0.05) { // 득표 수가 5% 인 경우에만 값 넣기
                votes[staffName - 'A'][0] = votesNum;
            }
        }

        // 1부터 14로 나눈 실수 구하기
        for (int s = 0; s < 26; s++)
            for (int i = 1; i <= 14; i++) {
                votes[s][i] = (float) (votes[s][0] / i);
            }

        //리스트에 모든 점수를 넣고

        List<Float> scores = new ArrayList<>();

        for (int s = 0; s < 26; s++) {
            if (votes[s][0] == 0.0) continue;
            for (int i = 1; i <= 14; i++) {
                scores.add(votes[s][i]);
            }
        }
		
        // 내림차순으로 정렬
        Collections.sort(scores, Collections.reverseOrder());

        for (int i = 0; i < 14; i++) {
            for (int s = 0; s < 26; s++) {
                if (votes[s][0] != 0.0) { // 14번째 점수까지만 돌고
                    for (int j = 1; j <= 14; j++) {
                        if (votes[s][j] == scores.get(i)) { // 일치하는 경우
                            votes[s][15] += 1.0; // 칩 주기
                            break;
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        
        // 값 출력
        for (int s = 0; s < 26; s++) {
            if (votes[s][0] == 0.0) continue;
            sb.append((char)(s + 65)).append(" " + (int) votes[s][15] + "\n");
        }

        System.out.println(sb);
    }
}