티스토리 뷰

알고리즘/BOJ

BOJ 13333, Q-인덱스

아테즈 2018. 10. 20. 20:50

@markdown

ACM-ICPC 2016년 대한민국 인터넷 예선에 출제되었던 문제입니다. 


Q-Index라는 개념을 이용해 문제를 푸는 것이었는데요.


번역문보다 원문을 보는게 이해가 빠른 문제라 푸는데 조금 시간이 걸렸던 문제입니다.


문제를 해설해보면


"Q 인덱스가 k이다" 라는 말은 


 " n개중에 k개의 논문이 k번 이상 인용되었고

   n-k의 논문이 k번 미만 인용되었다."


라는 의미입니다.


논문의 개수와 인용회수의 범위를 살펴보면,

논문의 개수 n은 1 이상 1000이하,

논문의 인용 회수(편의상 m)은 0이상 10000이하 라고 되어있습니다.


제가 생각하는 간단한 문제 풀이 방법은, 논문의 인용 횟수를 통해, 존재하는 논문을 전부 탐색해서, q-index의 최대값을 구하는 방법입니다.


Psuedo Code를 작성해보자면

```

for( i : paper1 ~ paper n){

    for( k : cited = 0 ~ cited = 10000){

        if( 인용회수of paper[i] >= k) over++;

        if( 인용회수of paper[i] < k) nonover++;

    }

    if(over >= k && nonover <= n-k){

        q = max(q,k);

    }

}

```


처럼 푸는 방법입니다.


위 방법처럼 문제를 해결하면 O(Nk)의 시간복잡도로 문제를 해결 할 수 있기 떄문에, 제한 시간 내로 문제를 해결할 수 있습니다.


아래는 소스코드입니다


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
 
    int n;
    vector<int> v;
    scanf("%d"&n);
    for (auto i = 0; i != n; i++) {
        int tmp; scanf("%d"&tmp);
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    int q = -1;
    for (auto i = 0; i != 10000 + 1; i++) {
        int over = 0;
        int nonover = 0;
 
        for (auto j = v.begin(); j != v.end(); j++) {
            if (*>= i) over++;
            else if (*< i) {
                nonover++;
 
            }
        }
        if (over >= i && nonover <= (n - i)) {
            q = max(q,i);
        }
    }
 
    cout << q;
 
    return 0;
}
cs





댓글
댓글쓰기 폼
공지사항
Total
21,136
Today
27
Yesterday
4
링크
TAG
more
«   2022/07   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
글 보관함