오늘의 코드. 3일차 (백준/25305번 커트라인)

 

작심삼일( 作心三日 )의 3일차. 여기서 끊어질 수 는 없다.
지금 이 커트라인을 넘어 가기위해 제목도 커트라인인 문제를 골라 보았다.

 

Baekjoon / Problem No. 25305  (커트라인)

 

Problem

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

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

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

Input

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

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

Output

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

---

Solution

사실 그냥 정렬을 하고 나서 k값에 해당하는 인덱스의 값을 출력하면 그것으로 끝이다. 정말 그것밖에 없다. 앗싸.

정렬등을 구현해도 괜찮지만 이번엔 <algorithm> 라이브러리의 sort() 를 사용하여 정렬은 Pass.

 

벡터를 이용하여 구현했다. 다만, sort() 함수는 오름차순 정렬이다 (Intro sort 기반의 오름차순 정리 함수)

커트라인을 구하려면 아무래도 내림차순인 것이 편하겠다. (배열의 음의 인덱스를 사용하거나 벡터의 back() 함수를 쓰는 방법도 있지만 어쨋든 분량상 알아봐야 할 것 같았다.) 

 

sort() 함수를 잘 살펴보자

sort ( start , end , compare )

start : iterator / pointer 에서 정렬을 시작 할 부분  = 배열, 벡터 등의 시작 부분
end  : iterator / pointer 에서 정렬을 마칠 부분      = 배열, 벡터 등의 끝 부분

compare : 정렬을 어떤 방법으로 할 것인지 정하는 부분

bool comp(int x, int y)
{
    return x < y;
}

int main()
{
    sort( 시작부분, 끝부분, comp )
}

 

이런 방식으로 Compare 부분에 직접 콜백함수를 넣어주면 비교 옵션을 바꿀 수 있다. (위 코드는 내림차순 정렬이다.)

또한, 간단한게 이런 임시 객체를 이용하는 방법도 있다고 한다.

#include <functional>

int main()
{
    sort( 시작부분, 끝부분, greater<>() )
}

----- greater의 내부----------
template< class T = void > // 타입은 추론됨 (C++ 14 이후)
struct greater;

 

여기서 greater<>() 라는 임시 객체는 functional 이라는 라이브러리에 저장되어있다.

반대로 less<>() 라는 임시 객체를 이용해 (이미 기본값이 오름차순이지만) 오름차순으로 명시적 지정이 가능하다.

 

이부분은 코딩 지식 게시판의 "오늘의 코딩지식. No. 1 (Sort()함수와 임시 객체)편" 에서 자세히 다루겠다.

 

이야기가 길어졌다. 코드부터 확인해보자.

---

Code

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
    int N, k = 0; 
    int now = 0;

    vector<int> num;
    scanf("%d %d", &N, &k);

    for (int i = 0; i < N; i++)
    {
        scanf(" %d", &now);
        num.push_back(now);
    }
    sort(num.begin(),num.end(),greater<>());
    printf("%d", num[k-1]);
    
}

코드의 사진이다.

---

Review

생각보다 간단한 부분에서도 더 나아가 임시 객체같은 새로운 개념들을 알게 되었고, 평소에 줄기차게 사용하는 sort() 함수에 대해서도 심도있게 알게 되었다. 분량을 늘려려고 아득바득 알아본거 아니다. 아무튼 아니다.