방과후
ALGORITHM NOTE약 2분

BOJ 2535 - 아시아 정보올림피아드

한 국가가 싹쓸이를 못하네

#algorithm#boj#silver#implementation#sorting
아카이브로 돌아가기

문제 링크

문제

최근 아시아 지역의 학생들만 참여하는 정보 올림피아드 대회가 만들어졌다. 이 대회는 온라인으로 치러지기 때문에 각 나라에서 이 대회에 참여하는 학생 수의 제한은 없다.

참여한 학생들의 성적순서대로 세 명에게만 금, 은, 동메달을 수여한다. 단, 동점자는 없다고 가정한다. 그리고 나라별 메달 수는 최대 두 개다.

예를 들어, 대회 결과가 다음의 표와 같이 주어졌다고 하자.

참가국학생번호점수
11230
12210
13205
21100
22150
31175
32190
33180
34195

이 경우, 금메달 수상자는 1번 국가의 1번 학생이고, 은메달 수상자는 1번 국가의 2번 학생이며, 동메달 수상자는 3번 국가의 4번 학생이다. (1번 국가의 3번 학생의 성적이 동메달 수여자보다 높지만, 나라 별 메달 수가 두 개 이하 이므로 1번 국가 3번 학생은 동메달을 받을 수 없다.)

대회 결과가 입력으로 주어질 때, 메달 수상자를 결정하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사이에 두고 주어진다. 단, 국가 번호는 1부터 순서대로 하나의 정수로 주어지며, 각 학생번호는 각 나라별로 1부터 순서대로 하나의 정수로 주어진다, 점수는 0 이상 1000 이하의 정수이고, 동점자는 없다고 가정한다. 입력으로 제공되는 국가는 적어도 두 나라 이상이다.

출력

메달을 받는 학생들을 금, 은, 동메달 순서대로 한 줄에 한 명씩 출력한다. 즉, 첫 번째 줄에는 금메달 수상자를, 두 번째 줄에는 은메달 수상자를, 세 번째 줄에는 동메달 수상자를 출력한다. 하나의 줄에는 소속국가 번호와 학생 번호를 하나의 빈칸을 사이에 두고 출력한다.

풀이

점수 순으로 메달을 주되, 같은 나라에서 최대 두 명까지만 받을 수 있다. 그래서 참가자들을 점수 내림차순으로 정렬한 뒤, 나라별로 몇 명이 이미 선발됐는지 세면서 앞에서부터 세 명을 뽑으면 된다.

현재 코드는 정렬 이후 국가별 카운트를 확인하며 메달리스트를 결정한다. 정렬이 끝나면 남는 조건은 '이 나라가 이미 두 번 나왔는가' 하나뿐이라 흐름이 꽤 단순하다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static class Node {
        int country, number, score;
        Node(int country, int number, int score) {
            this.country = country;
            this.number = number;
            this.score = score;
        }
    }
 
    private static Node[] nodes;
    private static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        nodes = new Node[N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
 
            int country = Integer.parseInt(st.nextToken());
            int number = Integer.parseInt(st.nextToken());
            int score = Integer.parseInt(st.nextToken());
 
            nodes[i] = new Node(country, number, score);
        }
 
        Arrays.sort(nodes, (n1, n2) -> n2.score - n1.score);
        solve(N);
        System.out.println(sb);
    }
 
    private static void solve(int N) {
        int cnt = 0;
        int[] count = new int[N + 1];
 
        for (Node node : nodes) {
            if (cnt == 3) break;
            if (count[node.country] == 2) continue;
 
            sb.append(node.country).append(" ").append(node.number).append('\n');
            cnt++;
            count[node.country]++;
        }
    }
}

복잡도

  • 시간 복잡도: 학생 기록을 점수 기준으로 정렬하므로 O(Nlog⁡N)O(N \log N)이다.
  • 공간 복잡도: 학생 기록을 저장하므로 O(N)O(N)이다.

마무리

점수 내림차순으로 훑되 나라별 선발 수만 제한하면 된다. 이미 두 명을 뽑은 나라는 건너뛰고 세 명이 채워지는 순간 멈추면 답이 완성된다.