[class2]백준 23246번(Sport Climbing Combined) - 코테공부 25일차(2025.02.16)

문제유형

정렬 알고리즘

풀이 방법 도출 과정

1. dict을 사용해서 매핑하고 최종 순위를 계산한 다음 그 순서에 따라 정렬하고

2. 3위이외에는 제거한 다음 결과를 출력하는 방법을 사용하도록 하겠다.

3. 그리고 세 종목 순위의 합산 점수가 낮은 선수가 이기는 것으로 하고 만약에 합산 점수도 같으면 등번호가 낮은 선수가 이긴다.

시간 복잡도

n번 나오는데 sorted함수가 사용되기 때문에 시간복잡도는 O(nlogn)이 된다. 가장 최악의 경우 n이 100인 경우이므로 100x7정도가 될 예정이다. 그러므로 시간복잡도 부분에서 걱정할 부분은 없다.

코드 및 간단설명

sorted함수의 key의 값을 사용하여 문제를 해결하였다.

n = int(input()) 
infos = [list(map(int, input().split())) for _ in range(n)]

sorted_infos = sorted(infos, key=lambda x: (x[1] * x[2] * x[3], x[1] + x[2] + x[3], x[0]))

for b, p, q, r in sorted_infos[:3]:
  print(b, end= ' ')

다른 풀이

1) 힙사용

이 문제는 힙을 사용하여 풀 수도 있다. 

import heapq

n = int(input())
heap = []

for _ in range(n):
    b, p, q, r = map(int, input().split())
    # 정렬 기준: (p*q*r, p+q+r, b)
    key = (p * q * r, p + q + r, b)
    heapq.heappush(heap, (key, b))

# 힙에서 가장 작은 3개의 항목을 꺼내서 b 값 출력
for _ in range(3):
    if heap:
        print(heapq.heappop(heap)[1], end=' ')