[Python] 백준 8979번 문제 풀이 - 올림픽

문제 링크

https://www.acmicpc.net/problem/8979

문제 이해

이 문제는 각 국가의 등수를 정하는데, 금메달 순으로 순위를 정하고, 금메달 개수가 같으면 은메달 개수, 은메달 개수가 같으면 동메달 개수를 비교해서 순위를 정합니다.

예를들어 메달 현황이 다음과 같이 완전 같은 경우가 나올 경우

 

	🥇	🥈	🥉
1번국가	1	1	1
2번국가	1	1	1
3번국가	0	0	0

1,2번국가가 공동 1등이 되고 3번국가가 3등이 되는 식으로 순위가 정해집니다.

아이디어

제가 생각한 아이디어는 다음과 같습니다.

1. 파이썬의 람다식을 사용하여 금, 은, 동 순으로 내림차순 정렬을 한다. → 금,은.동 순으로 정렬됨
2. 배열에 있는 것들을 하나씩 딕셔너리에 key(국가) : value(순위) 형식으로 저장한다.
3. 정렬했을 때 메달개수가 정확히 같은것은 붙어있을 것이기 때문에 이전 메달 현황과 비교하여 순위를 딕셔너리에 저장한다.
4. 주어진 국가의 순위를 딕셔너리에서 찾아 출력한다.

시간복잡도

정렬하는 것 : O(nlogn)

배열 순회하며 딕셔너리에 넣는 것 : O(n)

n은 최대 1000이기 때문에 가능합니다.

코드 구현

그래서 이 아이디어를 코드로 구현하면 다음과 같습니다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

# 나라별 메달 정보
countries = [tuple(map(int, input().split())) for _ in range(n)]

# 금, 은, 동 순으로 내림차순 정렬
countries.sort(key=lambda x: (-x[1], -x[2], -x[3]))
# 순위 저장 딕셔너리
rank_dict = {}

for i in range(n):
    current_country = countries[i]
    if i > 0 and current_country[1:] == countries[i-1][1:]:
        # 이전 나라와 메달 수가 모두 같다면, 이전 나라와 동일한 순위
        rank_dict[current_country[0]] = rank_dict[countries[i-1][0]]
    else:
        # 메달이 다르다면, 현재 위치가 새로운 순위
        rank_dict[current_country[0]] = i + 1

# 선택된 국가의 순위 출력
print(rank_dict[k])