[백준] 8979 올림픽 - 자바(Java)

 

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

8979번: 올림픽

 

 

 

 

각 국가별 이름, 금은동 메달 수가 주어지면 요구하는 국가의 순위를 출력하는 문제

난이도도 실버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