AlgorithmProgrammers

프로그래머스 H-index

, , , ,

1. 프로그래머스 H-index 문제

2. 컴퓨팅적 스킬

  • 정렬문제인 만큼 #include <algorithm> 헤더에 있는 sort를 이용하면 됩니다.
  • sort는 기본적으로 오름차순 정렬로 되어있습니다. 별 다른 옵션을 주지 않아도 오름차순 정렬을 하게 됩니다. 그 외 내림차순정렬을 이용 할 때는 다음과 같은 두가지 방법을 사용할 수 있습니다.

1.compare함수를 이용한 내림차순 방법

1
2
3
4
5
bool compare(int v1,int v2){
    return v1 < v2;
}
sort(citations.begin(),citations.end(),compare);

  1. greater() 함수 옵션을 사용한 내림차순 정렬
1
2
sort(citations.begin(),citations.end(),greater<int>());

3. 컴퓨팅적 사고

  • H-index의 개념을 알고가셔야 합니다. 논문 n편중 h번이상 인용된 논문이 h편이상이고 h번 이하 인용되었다면 h가 H-index가 됩니다.
  • 첫번째 테스트 케이스인 [3,0,6,1,5]로 예를 들어 설명하겠습니다.

오름차순 정렬 전

DATA INDEX
3 0
0 1
6 2
1 3
5 4

오름차순 정렬 후

DATA INDEX
0 0
1 1
3 2
5 3
6 4

4.

  • 정렬전과 정렬후의 과정입니다.H-index라는것을 맨처음에 모든 값의 합을 나눈 평균의 값이 H-Index라고 생각을 하여 아주 단순하게 생각했습니다. 당연히 틀린것이였습니다.
  • index를 가지고 생각했어야 했는데, 값을 가지고 생각을 하였습니다. 위의 테스트케이스는 총 5편의 논문이 쓰여졌으며 인덱스값이 DATA의 값보다 커지는 시점 index > data을 찾아야 합니다. 그 시점이 H-index지점입니다.데이터값은 뒤에서부터 비교하고 인덱스값은 앞에서 비교하게 됩니다. 따라서 citations.size()-i-1의 형식이 나오게됩니다. -1을 해주는이유는 for문에서는citiation-1지점까지만 순회하기때문에 이에 따라 -1을 붙여준것입니다. 어디서부터 시작하고 어디서부터 끝내는지에 대해서 한번더 고민해보시면 되겠습니다.
  • Data = 5, Index = 3의 지점이 H-index에 해당하는값 입니다. index>data의 지점에 index는 3의 값을 반환하게 됩니다. 이 값은 결국 h-index의 값을 나타내는것이며 총 5편의 논문과 3회이상의 인용된 논문 3편, 3회 이하 인용된 논문 2편이 되게 됩니다. 따라서 h-index의 값을 정확하게 도출해냈다고 할 수 있습니다.
  • 문제들을 너무 어렵게 생각하여 풀었는데, index에 대해 유연하게 접근하면 쉽게 풀 수 있었던 문제라고 생각합니다.

5. 풀이

5.1. 1. 정렬 풀이

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
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 오름차순 정렬, 내림차순은 그 반대 v1 > v2
bool compare(int v1,int v2){
    return v1 < v2;
}
int main(void){
    
    vector<int> citations;
    citations.push_back(3);
    citations.push_back(0);
    citations.push_back(6);
    citations.push_back(1);
    citations.push_back(5);
    
    
    sort(citations.begin(),citations.end(),compare);
    for(int i=0; i<citations.size(); i++){
        if(i >= citations[citations.size()-i-1]){
            cout << i;
            break;
        }
    }
  	return 0;
}
Share