- Problem Link : https://www.acmicpc.net/problem/1205
문제
- 리스트에 있는 점수, 새로운 점수, 랭킹 리스트에 올라갈 수 있는 점수의 개수가 주어질 때 새로운 점수가 몇 등인지 구하시오
- 만약 같은 점수가 있다면 그러한 점수의 등수 중에 가장 작은 등수가 된다.
- 단, 랭킹 리스트가 꽉 차있을때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다.
- 랭킹 리스트 안에 들지 못하면 -1을 출력한다.
입력
- 첫째줄, N, 새로운 점수, P가 주어진다.
- 둘째 줄, 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다.
출력
- 등수를 출력한다.
풀이
단순 while문을 이용해 새로운 점수가 어디에 위치해야하는지를 구한다. 이때 같은 점수의 경우에는 그 중 가장 작은 등수이므로 나보다 큰 점수일 때만 뒤로 인덱스를 미루면서 진행하면 된다. 이 때 인덱스는 0부터 시작이므로 결과 인덱스에 1을 더한 값이 내 새로운 랭킹이다.
이 때 이 등수가 P보다 작으면, 즉 랭킹 리스트에 든다면 출력하고 그렇지 않으면 -1을 출력하는 단순한 문제인 것 같지만 문제의 조건에 "랭킹 리스트가 꽉 차있을때 새 점수가 이전 점수보다 더 좋을때만 점수가 바뀐다"라는 조건을 만족시켜야한다.
이는 쉽게 말해 만약 내가 랭킹 리스트에 들어온다 하더라도 이전 점수와 같은 점수로 랭킹 리스트에 들어온다면 그것은 점수가 바뀌지 않는다는 것을 의미한다. 따라서 나와 같은 점수를 가진 점수들로 나머지 랭킹이 채워져있다면 나는 랭킹 리스트에 올라갈 수 없음을 의미한다. 따라서 각 케이스별로 상황을 나누어서 문제를 해결하자.
1. 내 랭크가 P보다 클때
- 이 때는 어떠한 반례도 없이 무조건 -1이다.
- 내가 무슨 짓을 해도 P안으로 들어갈 수가 없다.
2. 내 랭크가 P보다 작을때 (나랑 같은 점수가 없음)
- 나와 같은 점수가 없는데 내가 P 안에 들어온다는 것은 나보다 작은 점수가 랭킹 P 안에 있었다는 뜻이다.
- "따라서 조건의 새 점수가 이전 점수보다 더 좋을때"이므로 내 랭킹이 P 안의 점수와 정상적으로 바뀌게 되고 따라서 내 랭크를 출력한다.
3. 내 랭크가 P보다 작을때 (나랑 같은 점수가 있음)
-
나와 같은 점수가 있으면 P 안에 나보다 작은 점수가 있는지를 반드시 확인해야한다.
-
이를 확인하기 위해 나와 같은 점수를 가진 점수들 중 마지막 점수의 등수가 P의 범위 안에 들어오는지 아닌지 여부를 확인했다.
-
나와 같은 점수 중 마지막 점수가 P등 안에 들어올 때, 나보다 작은 점수가 하는 반드시 P안에 있다.
- 따라서 새로운 내 점수가 이전 점수보다 더 좋아야한다는 조건을 만족하므로 내 랭크를 출력
-
나와 같은 점수 중 마지막 점수가 P등 안에 못 들어올때, 나보다 작은 점수가 P 안에 없다.
- 따라서 새로운 내 점수가 이전 점수와 같은 점수이므로 점수가 바뀌지 않는다.
코드
import sys
input = sys.stdin.readline
n, score, p = map(int, input().split())
if n == 0:
print(1)
exit()
rank = list(map(int, input().split()))
i = 0
while i < n and rank[i] > score:
i += 1
my_rank = i + 1
if my_rank > p:
print(-1)
else:
same_score = list(filter(lambda x: rank[x] == score, range(len(rank))))
if same_score and same_score[-1] + 1 >= p:
print(-1)
else:
print(my_rank)
