백준 2817 - ALPS식 투표

www.acmicpc.net](https://www.acmicpc.net/problem/2817

2817번: ALPS식 투표

 

---

문제

백준 2817

칩을 주는 방식을 이해하는 데 꽤 오래 고민하게 한 문제입니다.

정렬보다는 구현에 가까운 알고리즘 문제였던 것 같아요.

풀이

1. 스태프 클래스 정의

static class Staff {
    String name;
    int votes;
    int chip = 0;
    Queue<Integer> arr = new LinkedList<>(); // 점수 집합

    public Staff(String name, int votes) {
        this.name = name;
        this.votes = votes;
    }
}

스태프의 이름과 득표수, 칩의 개수, 점수 집합을 가지는 클래스를 미리 정의했습니다.

여기서 점수 집합은 비교하면서 하나씩 제거하기 위해 Queue로 생성했습니다.

 

2. 득표율 5% 미만의 스태프 제외하기

for (int i = 0; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    String name = st.nextToken();
    int votes = Integer.parseInt(st.nextToken());
    // 득표율 5퍼 미만인 스태프는 제외
    if (5 < votes / X * 100.0) {
        list.add(new Staff(name, votes));
    }
}

입력값을 처리하면서 조건 중 하나인 5% 미만의 스태프를 제외할 수 있도록 같이 작성했습니다.

5% 이상인 스태프만 ArrayList에 추가합니다.

 

3. 스태프 이름 순 정렬하기

list.sort((Comparator.comparing(o -> o.name))); // 스태프 이름 순으로 정렬

출력하는 순서는 스태프 이름의 사전순이어야 하며 항상 알파벳 대문자로 들어오기 때문에 Comparator를 사용해 쉽게 정렬할 수 있습니다.

 

4. 스태프의 점수 집합 구하기

 for (Staff staff : list) {
    for (int j = 1; j <= 14; j++) {
        staff.arr.offer(staff.votes / j);
    }
}

각각의 스태프가 가진 점수 집합 Queue에 점수를 추가합니다.

 

5. 칩 나눠주기

int cnt = 1;
while (cnt <= 14) {
    int max = 0;
    int num = 0; // 가장 점수 집합이 높은 스태프를 찾기 위한 변수
    for (int i = 0; i < list.size(); i++) {
        Staff staff = list.get(i);
        int peek = staff.arr.peek();
        if (peek > max) {
            max = peek;
            num = i;
        }
    }
    Staff staff = list.get(num);
    staff.arr.poll(); // 점수 집합에서 제거
    staff.chip++;
    cnt++;
}

list.forEach(staff -> System.out.println(staff.name + " " + staff.chip));

총 14개의 칩을 나눠줄 것이기 때문에 14번 반복하도록 while문을 작성했습니다.

max는 각 스태프의 점수 집합 중 가장 높은 점수를 마킹하는 변수고 num은 max 값을 가진 스태프의 index를 담는 변수입니다.

스태프의 Queue에서 하나씩 꺼내서 비교하고 가장 높은 점수 집합을 가진 스태프의 Queue를 하나씩 제거하면서 칩을 추가했습니다.

 

정리

칩을 나눠주는 방식이 이게 뭐야하면서 꽤 고민을 했는 데 막상 풀어보니 그럭저럭 풀 만한 문제였습니다.

더 나은 방식이 있다면 피드백 주시면 감사하겠습니다.