문제 설명
전대프연에서는 스태프에게 수고비를 공정하게 지급하기 위해
ALPS 방식을 사용한다.
과정은 다음과 같다.
- 전체 참가자의 5% 미만 득표 스태프 제거
- 남은 스태프마다
득표수 / 1, /2, /3, ... /14총 14개의 점수를 만든다
- 전체 점수 중 상위 14개를 뽑는다
- 해당 점수를 가진 스태프에게 칩 1개씩 지급
입력
첫째 줄
X전체 참가자 수
둘째 줄
N스태프 수
다음 N줄
이름 득표수출력
조건을 만족하는 스태프에 대해
이름 칩개수사전순으로 출력
문제 해결 아이디어
핵심은 다음이다.
모든 후보의 점수를 하나의 리스트로 만들고
상위 14개를 뽑는다즉,
완전탐색 + 정렬 문제이다.
내가 작성한 코드
나는 각 후보별 점수를 리스트로 관리하고
매번 최대값을 찾아서 칩을 배분하는 방식으로 구현했다.
코드
import java.util.*;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
int N = sc.nextInt();
TreeMap<Character, List<Integer>> map = new TreeMap<>();
TreeMap<Character, Integer> result = new TreeMap<>();
for(int i = 0; i < N; i++) {
String c = sc.next();
int point = sc.nextInt();
if(point /(double) X * 100 < 5)
continue;
List<Integer> score = new ArrayList<>();
for(int j = 1; j <= 14; j++) {
score.add(point / j);
}
map.put(c.charAt(0), score);
result.put(c.charAt(0), 0);
}
for(int i = 0; i < 14; i++) {
int max = 0;
char maxKey = ' ';
for (Map.Entry<Character, List<Integer>> entry : map.entrySet()) {
char key = entry.getKey();
List<Integer> list = entry.getValue();
if(list.get(0) > max) {
max = list.get(0);
maxKey = key;
}
}
result.put(maxKey, result.getOrDefault(maxKey, 0)+1);
map.get(maxKey).remove(0);
}
for(Map.Entry<Character, Integer> entry : result.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}강의 코드
강의에서는 모든 점수를 하나의 배열로 만든 후
정렬해서 상위 14개를 선택하는 방식으로 해결했다.
코드
import java.util.Scanner;
class Main
{
static class Score{
Score(int staffIndex, double scr) {
this.staffIndex = staffIndex;
this.scr = scr;
}
int staffIndex;
double scr;
}
public static void sortScoresDescendingOrder(Score[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i].scr > arr[j].scr) {
Score cur = arr[i];
for (int k = i; k > j; k--)
arr[k] = arr[k - 1];
arr[j] = cur;
}
}
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
int N = sc.nextInt();
double validCut = X * 0.05;
boolean[] validCandidate = new boolean[26];
int[] staffVote = new int[26];
int candidateCount = 0;
for (int i = 0; i < N; i++) {
String name = sc.next();
int vote = sc.nextInt();
if (vote >= validCut) {
int index = name.charAt(0) - 'A';
validCandidate[index] = true;
staffVote[index] = vote;
candidateCount++;
}
}
Score[] scores = new Score[candidateCount * 14];
int scoreIndex = 0;
for (int i = 0 ; i < 26; i++) {
if (validCandidate[i]) {
for (int j = 1; j <= 14; j++)
scores[scoreIndex++] = new Score(i, (double)staffVote[i] / j);
}
}
sortScoresDescendingOrder(scores);
int[] ans = new int[26];
for (int i = 0; i < 14; i++)
ans[scores[i].staffIndex]++;
for (int i = 0; i < 26; i++) {
if (validCandidate[i])
System.out.println((char)(i + 'A') + " " + ans[i]);
}
}
}내 코드 vs 강의 코드 비교
1. 점수 처리 방식
내 코드
후보별 리스트 유지
→ 매번 최대값 탐색
→ 제거강의 코드
모든 점수를 하나로 모음
→ 정렬
→ 상위 14개 선택핵심 차이
| 방식 | 특징 |
|---|---|
| 내 코드 | 반복적으로 최대값 찾기 |
| 강의 코드 | 한 번 정렬로 해결 |
2. 시간복잡도 차이
내 코드
14번 반복 × 후보 수 탐색→ 대략
O(14 × N × 후보수)강의 코드
전체 점수 생성 + 정렬→
O(N log N)3. 자료구조 차이
| 항목 | 내 코드 | 강의 코드 |
|---|---|---|
| 자료구조 | TreeMap + List | 배열 |
| 정렬 방식 | 직접 탐색 | 정렬 |
| 구현 난이도 | 높음 | 낮음 |
4. 중요한 구현 차이
내 코드 문제점
score.add(point / j);→ 정수 나눗셈 사용
하지만 실제 문제는
실수 비교이므로 정확도 문제가 발생할 수 있다.
강의 코드
(double)staffVote[i] / j→ 정확한 비교 가능
핵심 개념
1. 보수값이 아니라 점수 집합 문제
이 문제는 단순 비교가 아니라
모든 점수를 만들어서 비교하는 문제2. 정렬 활용
상위 K개 문제 → 정렬 or 우선순위 큐3. 실수 계산 중요
정수 나눗셈 vs 실수 나눗셈시간 복잡도
강의 코드 기준
O(N × 14 + 정렬)→ 충분히 빠름
정리
이 문제는 처음 보면 복잡해 보이지만
핵심은 다음이다.
모든 점수를 만들고
가장 큰 14개를 선택한다내 코드는 매번 최대값을 찾는 방식으로 구현했지만,
강의 코드처럼
모든 값을 모아서 정렬하는 방식이 더 직관적이고 안정적이다.
또한
정수 나눗셈이 아니라 실수 나눗셈을 사용해야 정확한 비교가 가능하다는 점도 중요한 포인트였다.
아는거 없는 전공자