백준 25305 커트라인 C/C++

커트라인 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

1024 MB

3943

2771

2590

72.085%

문제

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

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

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

입력

첫째 줄에는 응시자의 수 N$N$과 상을 받는 사람의 수 k$k$가 공백을 사이에 두고 주어진다.

둘째 줄에는 각 학생의 점수 x$x$가 공백을 사이에 두고 주어진다.

출력

상을 받는 커트라인을 출력하라.

제한

•  1≤N≤1000$1 ≤ N ≤ 1\,000$ 
•  1≤k≤N$1 ≤ k ≤ N$ 
•  0≤x≤10000$0 ≤ x ≤ 10\,000$ 

예제 입력 1 복사

5 2
100 76 85 93 98

예제 출력 1 복사

98

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

int main(void)
{
	int n,k;



	cin >> n>>k;
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	// 배열 arr의 전체 영역 정렬 
	MergeSort(arr, 0, n - 1);




	printf("%d", arr[n-k]);

	return 0;
}

 

 

이전에 풀었던 병합정렬에 있는 소스 그대로 가져와서 붙여넣고

 

오름차순으로 정렬돼있어서 n-k번째 값을 printf한다.