Table of Contents
문제
각 국가별 메달 획득 수가 주어진다. 등수는 자신보다 성적이 좋은 국가의 수 + 1로 정한다. 주어진 국가 중 특정 국가의 등수를 계산하라.
예제
예제 1
입력:
4 3
1 1 2 0
2 0 1 0
3 0 1 0
4 0 0 1
출력: 2
예제 2
입력:
4 2
1 3 0 0
3 0 0 2
4 0 2 0
2 0 2 0
출력: 2
상황 파악과 계획
필요한 것: 성적 순 정렬, 특정 국가 찾기, 동점자 제외 계획: 금, 은, 동, 국가번호 순으로 튜플을 만들어 정렬. 정렬 결과에서 원하는 국가 찾은 후 해당 인덱스로 등수 계산, 거슬러 올라가며 동점자의 수만큼 등수 차감.
풀이
정답(100점) 확인까지는 약 30분 걸렸다.
1. 제출 오답
계획과 유사하게 쓰긴 했는데 인덱스로 등수를 계산하는 과정에서 반례가 발생했다.
모든 국가가 동점이거나, 자신이 1등이라 앞 순위가 없는 경우 등 if lis[i][:3] != lis[idx][:3]: 안으로 들어갈 기회가 없으면 등수 값이 업데이트되지 않아 답이 0으로 출력된다.
이 답안은 예제 입출력만 통과했다(100점 만점에 8점).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n, k = map(int, input().split(' '))
lis = []
rank = 0
idx = 0
for i in range(n):
country, gold, silver, bronze = map(int, input().split(' '))
lis.append((gold, silver, bronze, country))
lis = sorted(lis, reverse=True)
for i in range(n):
if lis[i][3] == k:
idx = i
break
for i in range(idx - 1, -1, -1):
if lis[i][:3] != lis[idx][:3]:
rank = i + 2
break
print(rank)
2. 제출 정답
등수를 계산하는 부분을 바꿔, 국가를 처음 찾았을 때부터 등수를 설정하고 동점자가 발견될 때마다 하나씩 차감하게 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n, k = map(int, input().split(' '))
lis = []
rank = 0
idx = 0
for i in range(n):
country, gold, silver, bronze = map(int, input().split(' '))
lis.append((gold, silver, bronze, country))
lis = sorted(lis, reverse=True)
for i in range(n):
if lis[i][3] == k:
idx = i
rank = i + 1
break
for i in range(idx - 1, -1, -1):
if lis[i][:3] == lis[idx][:3]:
rank -= 1
else:
break
print(rank)
3. 최단시간 답안
내 답안도 통과를 하긴 했는데, 왠지 조금만 고치면 더 나은 답이 될 것 같아서 최단시간 답안을 찾아봤다. 원래 답안은 등수를 정렬할 때 국가 번호도 같이 정렬되어서 국가 번호가 작을수록 뒤로 가는 문제가 있었는데 이 답안은 딱 필요한 국가만 따로 저장함으로써 아예 국가 번호가 필요 없게 만들었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
medals = []
for _ in range(n):
x, g, s, b = map(int,input().split())
medals.append((g, s, b))
if x == k:
k = (g, s, b)
medals.sort(reverse=True)
for i in range(n):
if medals[i] == k:
print(i+1)
break