[개쉬운 풀이] 백준 1205 등수 구하기

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

1205번: 등수 구하기

 

문제

태수가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.

이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.

예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다

랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다. 그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 태수의 새로운 점수가 주어진다. 이때, 태수의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그램을 작성하시오. 만약 점수가 랭킹 리스트에 올라갈 수 없을 정도로 낮다면 -1을 출력한다.

만약, 랭킹 리스트가 꽉 차있을 때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다.

 

생각

처음에 '비오름차순'으로 저장이 된다고 하여 정렬이 되지 않다고 판단하여 sort()를 통해 내림차순으로 재정렬하였다. 그러나, '비오름차순'은 내림차순과 비슷하지만 중복되는 값이 있을 때 '비오름차순'이라는 것을 배웠다. 

 

따라서 정렬된 상태이기 때문에 단순한 구현문제이다. 맨 앞부터 새로운 점수와 비교하면서 새로운 점수의 자리를 찾아주었다. 또한 새로운 점수와 중복된 값만큼 등수가 바뀌므로 이 부분도 고려해주었다.

 

또한 입력값에서 모든 점수는 2,000,000,000보다 작거나 같은 자연수 이므로 long long을 사용해주었다.

 

 

코드

int n, newScore, p;
vector<ll> list;

//list를 문제에 맞게 크기를 설정해줌
void input(){
    cin >> n >> newScore >> p;
    list.resize(p+1,-1);
    
    //인덱스를 1부터 N까지 사용하기 때문에 0번째 인덱스에는 2,000,000,000보다 큰 값을 넣어 0번째 인덱스를 고정함
    list[0] = 2000000001;
    for(int i = 1; i <= n; i++){
        cin >> list[i];
    }
}

bool cmp(ll a, ll b){
    return a > b;
}

resize()함수를 이용할 때 무슨 값으로 초기화를 할지 잘 고려해야한다. 다음과 같은 경우 값이 0이 존재할 수 있기 때문에 -1로 초기화를 해주었다.

 

 

//vector<ll> list;
void sol(){
	//문제에서 비오름차순으로 정렬이 되어있으므로 안해도 됌
    sort(list.begin(), list.end(), cmp);
    
    int ranking = -1;
	
    //새로운 점수를 상위 점수부터 비교해가며 자리를 찾아줌
    for(int i = 1; i <= p; i++){
        if(list[i] < newScore){
            list[i] = newScore;
            ranking = i;
            break;
        }
    }
    
    //새로운 점수가 랭킹에 드는 경우
    if(ranking != -1){
    	//새로운 점수와 동점인 경우를 해결해줌
        for(int i = ranking; i >= 0; i--){
            if(list[i] != newScore){
                ranking = i + 1;
                break;
            }
        }
    }
    cout << ranking << endl;
}

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

int n, newScore, p;
vector<ll> list;

void input(){
    cin >> n >> newScore >> p;
    list.resize(p+1,-1);
    list[0] = 2000000001;
    for(int i = 1; i <= n; i++){
        cin >> list[i];
    }
}

bool cmp(ll a, ll b){
    return a > b;
}

void sol(){
    sort(list.begin(), list.end(), cmp);
    
    int ranking = -1;

    for(int i = 1; i <= p; i++){
        if(list[i] < newScore){
            list[i] = newScore;
            ranking = i;
            break;
        }
    }
    if(ranking != -1){
        for(int i = ranking; i >= 0; i--){
            if(list[i] != newScore){
                ranking = i + 1;
                break;
            }
        }
    }
    cout << ranking << endl;
}

int main(){
    input();
    sol();
    return 0;
}

 

 

예외 케이스

--입력--

1 1 10

1

--결과--

1

 

--입력--

0 1 10

--결과--

1