백준 13333번 Q-인덱스

🔒문제 url

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

🪄전체 코드

#include <iostream>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);

int n;
int paper[1001];

void INPUT()
{
    IAMFAST
    cin >> n;
    for (int i = 0; i < n; i++) cin >> paper[i];
}


void solution()
{
    //정렬 시 최초로 k번 이상 인용한 논문의 index를 통해 k번 이상 인용한 논문의 총 갯수를 알 수 있다.
    sort(paper, paper + n);

    for (int k = 0; k < paper[n - 1]; k++)
    {
        //k번 이상 인용한 논문의 수, k번 이하 인용한 논문의 수
        int overK = n, underK = 0;
        for (int i = 0; i < n; i++)
        {
            if (paper[i] <= k) underK++, overK--;
            if (paper[i] >= k)
            {
                //위 조건문에서 k와 같을 때도 감소시켰으므로, 다시 1 증가
                overK++;
                break;
            }
        }

        //k번 이상 인용한 논문의 수가 k보다 크고, k번 이하 인용한 논문의 수가 n - k 이상이어야 한다.
        if (k <= overK && underK >= n - k)
        {
            cout << k;
            break;
        }
    }
    //모든 논문의 인용횟수가 0일 경우, 반복문을 돌지 않으므로 예외 처리
    if (paper[n - 1] == 0) cout << 0;
}

int main()
{
    INPUT();
    solution();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.