[Algorithm] 백준 13333 Q-인덱스 풀이

문제 설명

문제를 이해하는데 조금 걸렸다.

k번 이상 인용된 논문이 k편 이상이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다.

위의 말은 논문 인용 횟수를 오름차순으로 정렬하고(밑의 코드의 vector<int> v), k가 인용횟수의 어느 위치에 있는지 찾아준다(내부 for문). 이 부분은 k를 기준으로 인용횟수의 왼쪽과 오른쪽이 나누어서 조건을 파악하기 위해서이다. 이부분을 만족하는 최대의 k값을 구한다.

 

 

---

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    
    int n;
    scanf("%d", &n);
    vector<int> v;
    v.resize(n);
    
    for(int i = 0; i < n ; i++)
    {
        scanf("%d",&v[i]);
    }
    
    sort(v.begin(),v.end());

    int max = -1;
    for(int k = 0; k <= n; k++)
    {
        for(int i = 0; i < n; i++)
        {
            if(v[i] >= k && k <= n-i && n-k <= i+1)
            {
            	//k가 vector에서 어디에 위치하는지 찾은 후
                //i의 왼쪽과 오른쪽의 개수가 만족하면 max값을 바꿔준다.
                max = k;
            }
        }
    }
    
    printf("%d\n",max);
    
}