[백준] 8979 올림픽 - 자바(Java)
https://www.acmicpc.net/problem/8979
8979번: 올림픽
입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각
www.acmicpc.net
각 국가별 이름, 금은동 메달 수가 주어지면 요구하는 국가의 순위를 출력하는 문제
난이도도 실버5이고 간단한 문제처럼 보였지만 막상 풀어보면 간단하지 않았다.
특히 '금은동 메달 수 가 같으면 두 나라의 등수는 같다' 조건을 처리하는 부분이 까다로웠다.
풀이
먼저 CompareTo 메소드를 오버라이드 해 정렬규칙을 정해야 한다.
static class Nation implements Comparable<Nation> {
private int name;
private int gold;
private int silver;
private int bronze;
private int rank;
public Nation(int name, int gold, int silver, int bronze) {
super();
this.name = name;
this.gold = gold;
this.silver = silver;
this.bronze = bronze;
this.rank = 1; // 처음 순위는 1부터 시작
} // constructor
// 갯수가 같으면 금, 은, 동 순으로 내려가면서 비교
@Override
public int compareTo(Nation o) {
if(this.gold == o.gold) {
if(this.silver == o.silver) {
return o.bronze - this.bronze;
} else {
return o.silver - this.silver;
} // if-else
} else {
return o.gold - this.gold;
} // if-else
} // compareTo
} // end class:Nation
국가의 이름, 금은동 메달 수, 순위를 저장할 클래스를 만들고 Comparable 인터페이스를 구현한다.
금, 은, 동 순으로 비교하고, 갯수가 같을 때마다 하위 메달로 내려가며 순서를 정렬한다.
매개변수로 받은 필드에서 원래의 필드를 빼는 이유는 내림차순 정렬을 하기 위해서이다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
List<Nation> medalList = new ArrayList<>();
for(int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
int name = Integer.parseInt(st.nextToken());
int gold = Integer.parseInt(st.nextToken());
int silver = Integer.parseInt(st.nextToken());
int bronze = Integer.parseInt(st.nextToken());
Nation nation = new Nation(name, gold, silver, bronze);
medalList.add(nation);
} // for
Collections.sort(medalList);
...
주어진 정보를 Nation클래스에 저장하고, ArrayList에 추가했다.
compareTo메소드를 오버라이드 했기 때문에 sort메소드를 사용하면 재정의했던 규칙대로 정렬된다.
for(int i=1; i<n; i++) {
// 국가 두개씩 비교해서 rank를 정함
Nation originN = medalList.get(i-1);
Nation nextN = medalList.get(i);
if(originN.gold == nextN.gold &&
originN.silver == nextN.silver &&
originN.bronze == nextN.bronze) {
nextN.rank = originN.rank;
} else {
nextN.rank = i + 1;
} // if-else
} // for
medalList.stream().
filter(t -> t.name == k).
map(t -> t.rank).
forEach(System.out::println);
이부분이 문제의 핵심이다.
국가 두개씩 비교해가면서 금은동 메달의 수가 모두 같으면 다음 국가에 이전 국가의 순위를 그대로 대입한다.
나머지 경우에는 다음국가의 순위는 (이전 국가들의 합 + 1)로 설정한다.
왜 for문의 i + 1이 그 역할을 하냐면, 이미 메달 수 대로 국가들을 정렬 해두었고, 거기서 첫번째 국가부터 차례로 반복문이 돌아가기 때문에 i가 가리키는 숫자는 상위순위 국가의 갯수가 된다. 내가 위치한 순위는 그보다 하나 아래이기 때문에 +1을 해준다. 이렇게 설정하면 만약 중간에 동일한 순위의 국가가 있어도 (예를들어 1위 2위 2위 4위) 영향받지 않고 그대로 4위를 출력할 수 있다.
반복이 끝나면 문제에서 요구하는 국가의 이름을 찾아 해당하는 순위를 출력한다.
전체 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Nation implements Comparable<Nation> {
private int name;
private int gold;
private int silver;
private int bronze;
private int rank;
public Nation(int name, int gold, int silver, int bronze) {
super();
this.name = name;
this.gold = gold;
this.silver = silver;
this.bronze = bronze;
this.rank = 1; // 처음 순위는 1부터 시작
} // constructor
// 갯수가 같으면 금, 은, 동 순으로 내려가면서 비교
@Override
public int compareTo(Nation o) {
if(this.gold == o.gold) {
if(this.silver == o.silver) {
return o.bronze - this.bronze;
} else {
return o.silver - this.silver;
} // if-else
} else {
return o.gold - this.gold;
} // if-else
} // compareTo
} // end class:Nation
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
List<Nation> medalList = new ArrayList<>();
for(int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
int name = Integer.parseInt(st.nextToken());
int gold = Integer.parseInt(st.nextToken());
int silver = Integer.parseInt(st.nextToken());
int bronze = Integer.parseInt(st.nextToken());
Nation nation = new Nation(name, gold, silver, bronze);
medalList.add(nation);
} // for
Collections.sort(medalList);
for(int i=1; i<n; i++) {
// 국가 두개씩 비교해서 rank를 정함
Nation originN = medalList.get(i-1);
Nation nextN = medalList.get(i);
if(originN.gold == nextN.gold &&
originN.silver == nextN.silver &&
originN.bronze == nextN.bronze) {
nextN.rank = originN.rank;
} else {
nextN.rank = i + 1;
} // if-else
} // for
medalList.stream().
filter(t -> t.name == k).
map(t -> t.rank).
forEach(System.out::println);
} // main
} // end class