백준 25305번 : 커트라인(B2)

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

✨  문제 

2022 연세대학교 미래캠퍼스 슬기로운 코딩생활에 N명의 학생들이 응시했다.

이들 중 점수가 가장 높은 k명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.

커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다.

 

내 코드

import sys
import random
input = sys.stdin.readline

# def quick(array) :
#     if len(array) <=1 :
#         return array
    
#     pivot = array[0]
#     less = [x for x in array[1:] if x <=pivot]
#     greater = [x for x in array[1:] if x > pivot]
#     return quick(less) + [pivot] + quick(greater)

def quick(array):
    if len(array) <= 1:
        return array

    pivot = random.choice(array)  # 랜덤 피벗 선택
    less = [x for x in array if x < pivot]
    equal = [x for x in array if x == pivot]
    greater = [x for x in array if x > pivot]
    return quick(less) + equal + quick(greater)

def main() :
    n, k = map(int, input().rstrip().split())


    array = list(map(int, input().rstrip().split()))
    array = quick(array)
    #array = sorted(array)
    cutline = array[-k]
    print(cutline)


if __name__ == "__main__" :
    main()

 

느낀점

1.  파이썬 정렬 sorted는 아주아주 빠른 내장함수이다!

2. quick 정렬시 pivot을 초기 값으로 하는 것은 좋은 선택이 아니다. random을 애용하자