백준 2817번: ALPS식 투표 - [구현][정렬]

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

2817번: ALPS식 투표

문제가 넘나 넘나 넘나 헷갈렸던 것. (나만 그런가 ㅋㅠ)

칩을 분배하는 로직을 잘못 이해했었다. 

 

"점수 집합내에서  가장 큰 점수 가진 스태프한테 칩을 나눠준다."

점수 집합은 1로 나눈 값, 2로 나눈 값, ... 14로 나눈 값을 모~~두 하나로 합친 것이다.

그것을 내림차순 정렬해서 14번째까지의 주인에게 칩을 주는 것..

 

예를들어

테스트케이스가 아래와 같이 들어온다면,

235217
3
A 107382
C 18059
B 43265

이렇게 전체 집합에서 가장 큰 수 순서대로 14개를 뽑는 것이다.

 

 다른 예제를 보자면...

100
6
A 20
B 19
C 18
D 17
E 16
F 5

이런식으로 추려지게 된다.

 

 

 

암튼... 로직 방식을 깨달았으니 문제풀이 순서를 정리해보겠다.

//문제풀이 순서
1. 입력받기
1-1. 전체 투표수의 5%미만으로 득표한경우 제외 (탈락!)
2. 1~14로 나눈 점수 집합만들기(쭉쭉 쌓기)
3. 집합중에서 1~14번째로 가장 숫자가 큰 사람에게 칩 부여
4. 사전순으로 스태프와 보유한 칩 갯수 출력

Java 코드상에 문제풀이 순서대로 주석을 달아놓았으니 참고하기를..

 

package algorithm.boj;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Boj2817 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//1. 입력받기
		int allvotes = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		ArrayList<Staff> staffList = new ArrayList<Staff>();
		ArrayList<Score> scoreList = new ArrayList<Score>();
		
		//스태프 입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String name = st.nextToken();
			int vote = Integer.parseInt(st.nextToken());
			
			//1-1. 전체 투표수의 5%미만으로 득표한경우 제외 (탈락!)
			if(vote < (allvotes*0.05))
				continue;
			
			staffList.add(new Staff(vote, 0, name));
		}
		
		
		//2. 1~14로 나눈 점수 집합만들기
		for (int i = 1; i <= 14; i++) {
			
			//쭉쭉 쌓기
			for (int j = 0; j < staffList.size(); j++) {
				scoreList.add(new Score((staffList.get(j).vote)/i,j));
			}
			
			
		}

		//2. 집합 score기준 내림차순 정렬 
		Collections.sort(scoreList, new Comparator<Score>() {
			
			@Override
			public int compare(Score o1, Score o2) {
				if(o1.vote > o2.vote)
					return -1;
				else if (o1.vote == o2.vote) 
					return 0;
				else
					return 1;
			}
		});
		
		
		//3. 집합중에서 1~14번째로 숫자가 큰 사람에게 칩 부여
		for (int i = 0; i < 14; i++) {
			staffList.get(scoreList.get(i).idx).chip++;
		}

		//4. 사전순으로 스태프와 보유한 칩 갯수 출력
		Collections.sort(staffList, new Comparator<Staff>() {
			
			@Override
			public int compare(Staff o1, Staff o2) {
				if(o1.name.compareTo(o2.name) < 0) //아스키코드 기반 비교함 a-c면 왼쪽이 작기때문에 음수를 반환함
					return -1;
				else if (o1.name.equals(o2.name))
					return 0;
				else 
					return 1;
			}
		});
		
		for (int i = 0; i < staffList.size(); i++) {
			System.out.println(staffList.get(i).name + " " + staffList.get(i).chip);
			//					+ " " + staffList.get(i).vote);
		}
	}

}

class Staff {
	
	int vote =0;
	int chip =0;
	String name ="";
	
	Staff(int v, int c , String n) {
		this.vote = v;
		this.chip = c;
		this.name = n;
	}
}

class Score {
	
	float vote =0;
	int idx;
	
	Score(float v, int i) {
		this.vote = v;
		this.idx = i;
	}
	

}