[백준] S5 8919번 올림픽 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

[문제] 

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

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 이하이다.

[출력]

출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다. 

 

 

---

[풀이]

1. 국가의 정보를 담을 클래스를 만들어준다.

2. 정렬을 처리해야 하므로 Comparable을 implements를 해준다.

3. 정렬할 기준에 맞춰서 compareTo를 override 해준다.

4. 국가의 정보를 입력받아서 순서를 출력해준다.

5. 공통 순위에 대한 처리를 해주기 위해 기준 국가와 비교를 하며 같다면 등수를 바로 증가시키는 방법이 아닌 같은 국가의 수만큼 증가를 시키는 처리를 해주었다.

[접근]

1. 처음에 문제를 보고 그냥 정렬을 시키면 되겠다고 생각하고 쉽게 접근을 하였다.

2. 문제를 다시 보니 공통순위에 대한 처리가 필요해 이를 어떻게 처리해줘야 할지 고민했다.

3. 기준을 잡고 비교 대상을 비교하며, 현재의 기준과 비교대상의 금메달, 은메달, 동메달의 수가 동일하다면 중복을 처리하기 위한 count를 증가시켜준다.

4. 서로 다른 경우에는 랭킹을 증가시켜 준다. 여기서 공통을 체크하기 위한 count값이 0이 아니라면 그에 해당하는 수만큼 랭킹을 추가로 증가시켜준다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_S5_8919 {
	static int N; // 국가의 수
	static int K; // 국가의 번호
	static int ranking; // 등수
	
	static class Country implements Comparable<Country> {
		int C; // 국가 번호
		int G; // 금메달
		int S; // 은메달
		int B; // 동메달
		
		public Country(int c, int g, int s, int b) {
			C = c;
			G = g;
			S = s;
			B = b;
		}
		
		@Override
		public int compareTo(Country o) {
			if (G > o.G) // 금메달 내림차순 정렬
				return -1;
			else if (G == o.G) { // 금메달의 개수가 같으면
				if (S > o.S) // 은메달 내림차순 정렬
					return -1;
				else if (S == o.S) { // 은메달의 개수가 같다면
					if (B > o.B) // 동메달 내림차순 정렬
						return -1;
				}
			}
			return 1;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		// 우선순위큐에 담아주기
		PriorityQueue<Country> pq = new PriorityQueue<>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int index = Integer.parseInt(st.nextToken()); // 국가의 번호
			int g = Integer.parseInt(st.nextToken()); // 금메달
			int s = Integer.parseInt(st.nextToken()); // 은메달
			int b = Integer.parseInt(st.nextToken()); // 동메달
				
			pq.add(new Country(index, g, s, b));
		}
		
		// 1등부터 시작하니까 1
		ranking = 1;
		
		Country country = pq.poll();
		
		// 만약 1등인 경우라면 바로 출력해주기
		if (country.C == K) {
			System.out.println(ranking);
			System.exit(0);
		}
		
		// 아니라면 공동순위가 발생할 수 있으니까 아래에서 처리
		int equal = 0; // 공통의 수
		
		while (!pq.isEmpty()) {
			Country c = pq.poll(); // 비교할 대상을 빼낸다.
			
			// 만약에 금메달, 은메달, 동메달의 수가 같다면
			if (country.G == c.G && country.S == c.S && country.B == c.B) {
				equal++; // 공통 수를 증가
			}
			else { // 다르다면
				country = c; // 현재 비교하는 국가를 넣고  
				ranking++; // 랭킹을 증가시킨다.
				
				if (equal > 0) { // 만약 공통된 수가 있다면
					ranking += equal; // 랭킹을 그만큼 더 추가한다.
					equal = 0; // 공통 순위를 처리해줬으니 다시 0으로 초기화
				}
			}
			
			// 비교하는 국가가 알고싶은 국가라면 랭킹 출력 후 종료
			if (c.C == K) {
				System.out.println(ranking);
				System.exit(0);
			}
		}
	}
}