[백준 25305번] 커트라인 - python

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

📌 문제 탐색하기

목표

• n명의 응시자 점수 중 상위 k명을 선별
• 상을 받을 사람 중 가장 낮은 점수(커트라인)을 출력

입력값

• 응시자의 N(1 ≤ N ≤ 1000), 상 받는 사람의 수 k(1 ≤ k ≤ N)
• 각 학생의 점수 $x$ (0 ≤ $x$ ≤ 10000)
  • 한 줄에 공백을 주고 주어짐.

출력값

• 상을 받는 커트라인 점수

📌 코드 설계하기

해결 아이디어

• 점수 리스트를 내림차순으로 정렬
• k-1번 인덱스를 가진 점수 출력

📌 정답 코드

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

arr = list(map(int, input().split()))[:n]

arr.sort(reverse=True)
# print(arr)

print(arr[k-1])

시간 복잡도 계산해보기

• 입력 처리
  • map(int, input().split()) → O(N)
  • 슬라이싱 [:n] → O(N)
  • 합치면 O(N)
• 정렬
  • arr.sort(reverse=True) → 파이썬 내장 함수로 평균/최악 시간 복잡도 → O(N log N)
• k번째 요소 출력
  • 인덱스 접근 → O(1)

최종 시간 복잡도: O(N log N)

다른 풀이

• 힙 이용하기
  • 완전이진트리 형태의 자료구조
  • 항상 부모 노드 ≤ 자식 노드(최소힙) 혹은 부모 노드 ≥ 자식 노드(최대힙) 조건을 만족
  • root에는 항상 가장 작은 값(최소힙) 또는 가장 큰 값(최대힙)이 존재
  → 파이썬의 heapq는 최소힙만 지원하므로 가장 작은 값이 루트에 위치한다.
• 만약 최대힙을 쓰고 싶다면 모든 값을 음수로 변환해서 저장하면 된다.
• heapq의 특징
  • 내부적으로 List를 이용해서 힙을 구현한다.
  • 값이 들어올 때마다 O(log n) 시간에 자동으로 정렬된 힙 상태를 유지한다.
  → 전체를 정렬하지 않아도 필요한 만큼만 빠르게 유지 가능하기 때문에 시간 복잡도 문제를 완화할 수 있다.

import sys
import heapq

n, k = map(int, input().split())
scores = list(map(int, input().split()))[:n]

heap = []

for score in scores:
    if len(heap) < k:
        heapq.heappush(heap, score)
    else:
        if score > heap[0]:
            heapq.heapreplace(heap, score)

print(heap[0])