20.06.27 개발일지 - Q-인덱스

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

13333번: Q-인덱스

입력된 n개의 논문들의 인용 횟수를 받고 k | N(q(i) ≥ k) ≥ k, N(q(i) ≤ k) ≤ k (0 ≤ i ≤ n)인 k를 구하는 문제입니다.

 

제가 처음 선택한 풀이법은 다음과 같습니다.

1. 입력받은 리스트를 오름차순으로 정렬한다.

2. index를 순회하면서 q(i) ≥ i && q(i) ≤ n - i인지 확인을 한다.

3. 2의 조건이 만족할 경우, i 값을 저장한다.

4. 순회를 모두 마친 후 최후의 저장된 i값을 출력한다.

 

하지만 이 문제에는 몇가지 큰 문제점이 있었습니다.

1) Q-index 값이 입력된 논문의 인용 횟수 내로 제한된다.

2) 논문 인용 횟수가 논문 갯수보다 월등히 높으면 Q-index가 0으로 연산된다.

 

하지만 적은 것과 다르게 이를 알아내는데에는 6차례의 추가 시도가 필요했습니다.

 

그리고 결국 수정한 방안은 다음과 같습니다.

1. 입력받은 리스트를 오름차순으로 정렬한다.

2. 임의의 qindex를 Max(q(i))까지 순회한다.

3. 2의 순회에서 qindex보다 크거나 같은 q(i)를 갖는 index를 구한다.

4. index ≤ qindex && n - index ≥ qindex인 qindex를 저장한다.

5. 순회를 마치고 최종적으로 저장된 qindex를 출력한다.

 

문제 성격상 내림차순으로 정렬하여 qindex를 내림차순으로 순회하면 조금 더 빠르게 풀 수 있겠지만, 

이대로도 충분히 해결이 되기에 따로 수정을 하지는 않았습니다.

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

using namespace std;

int main()
{
    int size = 0, input = 0, output = 0, max = 0;
    vector<int> report;
    cin >> size;
    for (int i = 0; i < size; ++i)
    {
        cin >> input;
        report.push_back(input);
    }

    sort(report.begin(), report.end());
    max = report[size - 1];

    for (int qIndex = 0; qIndex < max; ++qIndex)
    {
        int index = 0;
        while (report[index] < qIndex)
        {
            ++index;
        }
        if ((index <= qIndex) && (size - index >= qIndex))
        {
            output = qIndex;
        }
    }

    cout << output << endl;

    return 0;
}