백준 25305번 풀이

문제

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

25305번: 커트라인

참가자 인원 수와 상을 타는 인원 수, 그리고 점수가 주어졌을 때 점수가 가장 낮은 사람을 출력하시오

 

풀이

보통 커트라인이라고 하면 수능이나 모평때 많이 쓰는 말인데, 9월 모평 1등급 등급컷이 얼마더라~ 이런 식으로 쓴다. 수능이나 모평의 등급컷은 전체적인 난이도와 참여 인원에 따라 달라지기때문에 똑같이 50점을 받았어도 난이도가 핵불닭수능이면 등급이 높고, 물수능이면 등급 망한다. 

아, 그거랑 별개로 이 문제는 대단히 쉽다. 입력받은 점수를 정렬하고 뒤에서 k번째인 원소를 뽑으면 되거든. 

import sys
N, k = map(int,sys.stdin.readline().split())

x = list(map(int,sys.stdin.readline().split()))

def merge_sort(array):
	if len(array) < 2:
		return array
	mid = len(array) // 2
	low_arr = merge_sort(array[:mid])
	high_arr = merge_sort(array[mid:])
    # 일단 짼다

	merged_arr = []
	l = h = 0
	while l < len(low_arr) and h < len(high_arr):
		if low_arr[l] < high_arr[h]:
			merged_arr.append(low_arr[l])
			l += 1
		else:
			merged_arr.append(high_arr[h])
			h += 1
	merged_arr += low_arr[l:]
	merged_arr += high_arr[h:]
	return merged_arr
    # 그리고 비교한다

print(merge_sort(x))

일단 잘못하면 응애 나 애기시간초과! 가 반길수도 있으니 빠름 빠름 빠름 LTE-빠름! 이라는 병합정렬을 가져와보자. 그리고 예시를 저기에 돌려보면 

5 2
100 76 85 93 98
[76, 85, 93, 98, 100]

정답이 98인데... 뒤에서 두번째에 있다. 

 

import sys
N, k = map(int,sys.stdin.readline().split())

x = list(map(int,sys.stdin.readline().split()))

def merge_sort(array):
	if len(array) < 2:
		return array
	mid = len(array) // 2
	low_arr = merge_sort(array[:mid])
	high_arr = merge_sort(array[mid:])
    # 일단 짼다

	merged_arr = []
	l = h = 0
	while l < len(low_arr) and h < len(high_arr):
		if low_arr[l] < high_arr[h]:
			merged_arr.append(low_arr[l])
			l += 1
		else:
			merged_arr.append(high_arr[h])
			h += 1
	merged_arr += low_arr[l:]
	merged_arr += high_arr[h:]
	return merged_arr
    # 그리고 비교한다

print(merge_sort(x)[-k])

그래서 정렬하고 뒤에서 k번째인 수를 뽑으면 되기 때문에 -k로 인덱싱 해 주면 된다. (-1이 뒤에서 첫번째)