[ 백준 ] 1205 / 등수 구하기

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
32/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 1205 / 등수 구하기
 *
 * Kind :: Simulation
 *
 * Insight
 * - 점수들이 비오름차순으로 주어지고
 *   새로운 점수를 끼워넣는 거라면
 *   Binary Search 를 활용해볼 수 있지 않을까?
 *   + 근데 오름차순이 아니라 비오름차순으로 점수가 정렬되어서 사용하기가 좀 껄끄럽다
 *     잠깐만, 거꾸로 보면 오름차순인데 이를 활용할 수 있지 않을까?
 *     Vector 보면 rbegin() 과 rend() 있잖아?
 *     # <algorithm> 의 lower_bound 를
 *       rbegin(), rend() 를 이용해서 사용할 수 있겠다!
 *
 * Point
 * - Vector 선언시 크기는
 *   N 이 아니라 P 로 정하면 생각하기 편하다
 *   + 문제 조건에 따라 N <= P 인데,
 *     전광판에 점수가 아직 덜 채워진 것으로 생각하면
 *     새로운 점수가 들어올 때 그 점수가 들어갈 수 있는지 판단해주면 된다
 *     # 점수들이 있고 그 점수들에 크기 P 의 마스크를 씌우는 방식으로도 생각할 수 있지만
 *       여기서는 항상 N <= P 이므로 이렇게 구현하면 조금 예외처리가 까다로워진다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, S, P;
    cin >> N >> S >> P;
    vector<int> L(P, -1); /* 랭킹 리스트에서 비어져있는 점수들을 -1 로 초기화 */
    for (int i=0; i<N; i++)
        cin >> L[i];

    // Process
    auto pos = lower_bound(L.rbegin(), L.rend(), S); /* 뒤에서 (pos+1) 번째 */
    int idx = P - (pos - L.rbegin()); /* 앞에서 (idx+1) 번째 */

    int ans = -1;
    if (idx < P) { /* 랭킹에 들어갈 수 있으면 */
        L[idx] = S; /* 랭킹 리스트 점수 갱신 */
        int G[P]; /* 랭킹 리스트 순위 갱신 */
        for (int i=0; i<P; i++) {
            G[i] = i+1;
            if (i > 0 && L[i] == L[i-1]) {
                G[i] = G[i-1];
            }
        }
        ans = G[idx];
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글