문제
랭킹 리스트에 새 점수가 추가될 때의 등수를 구한다. 같은 점수는 같은 등수를 가지며, 리스트가 가득 차면 진입 불가 시 -1을 출력한다.
입력
첫째 줄에 N(현재 점수 수), 새 점수 S, 최대 랭킹 수 P가 주어진다. N이 0이 아니면 둘째 줄에 N개의 점수가 비오름차순으로 주어진다.
출력
새 점수의 등수를 출력한다. 랭킹에 올라갈 수 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 90 10 100 90 80 | 2 |
0 100 10 | 1 |
풀이
기존 점수 배열을 순회하며 새 점수보다 높은 점수와 같은 점수의 개수를 세어 등수를 판별한다.
- N이 0이면 바로 1등을 출력한다
- 배열을 순회하며 새 점수 S보다 큰 점수의 수(ans)와 같은 점수의 수(tmp)를 센다
- ans + tmp가 P를 초과하면 리스트에 진입할 수 없으므로 -1을 출력한다
- 그렇지 않으면 ans + 1이 등수가 된다
핵심 아이디어: 등수는 자신보다 높은 점수의 수 + 1이며, 동점자가 있어도 같은 등수를 부여한다. 단, 리스트 크기 제한(P)을 초과하면 진입 불가이다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day751BOJ1205등수구하기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
if (N == 0) {
System.out.println(1);
return;
}
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int ans = 1;
int tmp = 0;
for (int i = 0; i < arr.length; i++) {
int k = arr[i];
if (k > S) {
ans++;
}
if (k == S) {
tmp++;
}
}
if (ans + tmp > P) {
System.out.println(-1);
return;
}
System.out.println(ans);
}
}복잡도
- 시간: O(N)
- 공간: O(N)