문제

---

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

코드

---

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		PriorityQueue<Country> pq = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			pq.add(new Country(br.readLine().split(" ")));
		}

		Country prev = pq.poll();
		if (prev.id == K) {
			System.out.println(1);
			return;
		}

		int rank = 2;
		int lastRank = 2;
		while (!pq.isEmpty()) {
			Country cur = pq.poll();

			if (!prev.equalTo(cur)) {
				lastRank = rank;
			}

			if (cur.id == K) {
				System.out.println(lastRank);
				return;
			}
			
			rank++;
			prev = cur;
		}
	}

	static class Country implements Comparable<Country> {
		int id;
		int gold;
		int silver;
		int bronze;

		Country(String[] input) {
			this.id = Integer.parseInt(input[0]);
			this.gold = Integer.parseInt(input[1]);
			this.silver = Integer.parseInt(input[2]);
			this.bronze = Integer.parseInt(input[3]);
		}

		@Override
		public int compareTo(Country o) {
			if (o.gold == this.gold) {
				if (o.silver == this.silver) {
					return Integer.compare(o.bronze, this.bronze);
				}
				return Integer.compare(o.silver, this.silver);
			}

			return Integer.compare(o.gold, this.gold);
		}

		public boolean equalTo(Country o) {
			return this.gold == o.gold && this.silver == o.silver && this.bronze == o.bronze;
		}

		@Override
		public String toString() {
			return String.valueOf(id);
		}
	}
}

문제 이해

---

• N개의 국가가 주어질 떄 id가 K인 국가의 등수를 출력하는 문제이다.
• 등수 판별은 금메달 개수가 가장 많은 국가부터 따지고, 만약 금메달 개수가 같다면 은메달, 은메다 개수가 같다면 동메달, 동메달까지 개수가 같다면 공동 순위로 처리한다.
• 예를 들어 2, 3번이 공동 2등이라면, 3등은 없고 4등부터 다시 점수를 매긴다.

풀이 방법

---

• 우선 등수를 매기는 로직을 적절히 CompareTo로 구현한다.
• 그 후, 객체를 priorityQueue에 삽입하고 id가 K인 국가를 뽑을 때까지 반복한다.
• 이때 단순히 뽑은 순서를 등수로 출력하면 오답이 나온다.
• 앞서 나온대로 공동 순위를 구현하기 위해 이전 국가와 현재 국가의 메달이 같은지 비교해야 한다.
• 매번 1씩 증가하는 인덱스를 rank, 가장 최근에 갱신된 등수를 lastRank라고 하자.
• 만약 이전 국가와 현재 국가의 메달 개수가 다르다면 lastRank는 rank로 갱신된다.
• 하지만 만약 두 국가의 메달 개수가 같다면, lastRank는 갱신되지 않는다. 이를 통해 공동 순위를 구현한다.
• 두 국가의 메달 개수가 같더라도, rank는 항상 증가한다. 따라서 공동순위 뒤에 위치한 국가는 자신에게 맞는 등수를 갖게 된다.

핵심 포인트

---

• 구현 자체는 compareTo + pq의 조합만 활용하면 금방 해결할 수 있는 문제이다.
• 하지만 공동 순위에 대한 부분을 충분히 읽지 않는다면 문제를 틀리게 된다.
• 공동 순위 처리에 유념하자.

보완할 점 / 느낀 점

---

• 위에서 언급한대로, 문제의 큰 틀은 pq + compareTo의 조합으로 쉽게 구현할 수 있었다.
• 하지만 의외로 공동 순위 처리 과정에서 많은 시간이 걸렸다.
• 어떻게 구현할지도 확인했고, 딱히 꼬아서 구현할 필요도 없이 for문과 if문만 적절히 사용하면 충분히 할 수 있는 구현이었는데 생각보다 시간을 오래 썼다.
• 위와 같이 공동 순위를 매기는 알고리즘도 익히고 있어야겠다. 쉽게 풀리는 문제라고 생각하여 손이 움직여지는대로 구현하다가, 생각보다 푸는데 오래 걸린 문제였다.

참고자료

---