문제
N개 국가의 금/은/동 메달 수가 주어질 때, K번 국가의 등수를 구하라. 금 → 은 → 동 순으로 비교하며, 같으면 동순위이다.
입력
첫째 줄에 N, K, 이후 N줄에 국가번호와 금/은/동 메달 수가 주어진다.
출력
K번 국가의 등수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 3 1 1 2 0 2 0 1 0 3 0 1 0 4 0 0 1 | 2 |
풀이
K번 국가보다 메달이 많은 국가의 수를 세어 등수를 구한다.
- 각 국가의 금/은/동 메달 수를 배열에 저장한다
- 모든 국가를 순회하며 K번 국가보다 금→은→동 순으로 비교하여 앞서는 국가를 센다
- 앞서는 국가 수 + 1이 등수이다
핵심 아이디어: 정렬 없이 K번 국가와 직접 비교하여 O(N)에 등수를 구한다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day447BOJ8979올림픽 {
static int N, K, ans;
static int[][] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N + 1][3];
ans = 1;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int id = Integer.parseInt(st.nextToken());
int g = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[id][0] = g;
arr[id][1] = s;
arr[id][2] = b;
}
for (int i = 1; i <= N; i++) {
if (arr[i][0] > arr[K][0])
ans++;
else if (arr[i][0] == arr[K][0] && arr[i][1] > arr[K][1])
ans++;
else if (arr[i][0] == arr[K][0] && arr[i][1] == arr[K][1] && arr[i][2] > arr[K][2])
ans++;
}
bw.write(String.valueOf(ans));
bw.flush();
br.close();
bw.close();
}
}복잡도
- 시간: O(N)
- 공간: O(N)