[백준_8979번] 올림픽

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

8979번: 올림픽

[문제]

 올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.

 

1. 금메달 수가 더 많은 나라 
2. 금메달 수가 같으면, 은메달 수가 더 많은 나라
3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 

 각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다. 

각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오.

 

[입력 조건]

 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.

 

[코드]

import java.util.*;

class team implements Comparable<team>{
	int teamnumber;
	int gold;
	int silver;
	int bronze;
	int rank;
	
	public team(int teamnumber, int gold, int silver, int bronze) {
		this.teamnumber=teamnumber;
		this.gold=gold;
		this.silver=silver;
		this.bronze=bronze;
	}
	
	@Override
	public int compareTo(team o) {
	    // 금매달의 개수가 같은 경우
		if(this.gold==o.gold) {
			// 은매달의 개수가 같은 경우
	         if(this.silver==o.silver) {
	        	 // 동매달의 개수로 순위 결정
	             return o.bronze-this.bronze;
	         }
	         // 은매달의 개수로 순위 결정
	         else {
	             return o.silver-this.silver;
	         }
	     }
		// 금매달의 개수로 순위 결정
	     else {
	         return o.gold-this.gold;
	     }
	 }
}

public class BaekJoon_8979 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		PriorityQueue<team> pq=new PriorityQueue<team>();
		
		for(int i=0;i<n;i++) {
			int num=sc.nextInt(); // 팀 번호
			int g=sc.nextInt(); // 금매달 개수
			int s=sc.nextInt(); // 은매달 개수
			int b=sc.nextInt(); // 동매달 개수
			
			pq.offer(new team(num,g,s,b));
		}
		
		// 1등인 나라를 큐에서 꺼낸다.
		team prev=pq.poll(); 
		prev.rank=1; 
		// 1등인 나라가 알고자하는 k 국가와 같은 경우
		if(prev.teamnumber==k) {
			System.out.println(prev.rank);
			return;
		}
		
		int rankcount=2; // 순위 count 변수
		while(!pq.isEmpty()) {
			team current=pq.poll();
			
			// 앞선 나라와 모든 매달의 개수가 같은 경우 
			if(prev.gold==current.gold
					&&prev.silver==current.silver
					&&prev.bronze==current.bronze) 
				// 같은 순위 유지
				current.rank=prev.rank;
			// 매달의 개수가 다르다면 +1등한 수 저장(2부터 시작했기 때문)
			else
				current.rank=rankcount;
			
			// 현재 팀의 번호가 알고자하는 k 국가라면 해당 국가의 랭킹 출력후 return
			if(current.teamnumber==k) {
				System.out.println(current.rank);
				return;
			}
			
			// 값 갱신
			rankcount++;
			prev=current;
		}
	}
}

 

[고찰]

 이번 문제는 각 팀마다 팀 번호, 금매달의 개수, 은매달의 개수, 동매달의 개수와 랭킹을 저장해야 하기 때문에 이를 담은 클래스를 선언하여 사용해야 한다. 또한 매달의 개수에 따라 정렬을 해야하기 때문에 클래스 내에서 오버라이딩을 통해 compare 함수를 재정의 해준다. 정렬이 완료된 팀들을 우선순위 큐에서 하나씩 꺼내 각 매달의 개수가 같은지 확인하고 매달의 개수가 이전의 팀과 같다면 랭킹을 유지하고, 아니라면 +1한 랭킹을 저장해주는 방식으로 구현한다면 100점을 받을 수 있다. 

 여태까지 풀어봤던 정렬 문제중에는 난이도가 높지는 않지만 팀당 저장해야 하는 변수들이 많아 클래스를 사용해야 한다는 것을 바로 생각하지는 못했다.