문제
각 참가자의 나라, 학생 번호, 점수가 주어질 때, 점수 내림차순으로 상위 3명을 선발하되 한 나라에서 최대 2명까지만 선발하라.
입력
첫째 줄에 N, 이후 N줄에 나라 번호, 학생 번호, 점수가 주어진다.
출력
선발된 3명의 나라 번호와 학생 번호를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 1 1 230 1 2 210 2 1 200 2 2 250 | 2 2 1 1 1 2 |
풀이
점수 내림차순으로 정렬 후, 같은 나라 2명 제한을 적용하며 상위 3명을 선발한다.
- 점수 내림차순으로 정렬한다
- 순서대로 탐색하며 같은 나라에서 이미 2명이 선발되었으면 건너뛴다
- 3명이 선발되면 종료한다
핵심 아이디어: 정렬 후 순차 탐색하면서 나라별 카운트만 관리하면 된다.
코드
package day649;
import java.io.*;
import java.util.*;
public class Day647BOJ2535정보올림 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][3];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[2] == o2[2]) {
if (o1[1] == o1[1])
return o2[0] - o1[0];
else
return o2[1] - o1[1];
} else
return o2[2] - o1[2];
}
});
int cnt = 0;
int c = 0;
for (int i = 0; i < 8; i++) {
if (i != 0) {
if (arr[i - 1][0] == arr[i][0])
cnt++;
else
cnt = 0;
}
if (cnt < 2) {
for (int j = 0; j < 2; j++) {
sb.append(arr[i][j]).append(" ");
}
sb.append("\n");
c++;
}
if (c == 3) {
break;
}
}
System.out.println(sb);
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)