프로그래머스 H-Index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

문제만 보면 생각보다 간단하게 느껴진다.

문제를 보면 조건이 여러 개인 것을 알 수 있다.

조건을 확인하기 위해 반복문을 여러 개 썼다가는 분명 시간 초과가 날 것이다.

때문에 어떻게 하면 문제를 효율적으로 접근할 수 있을지 생각해 보았다.

문제를 처음 보면 이해를 하고, 쉽게 푸는 방법을 고려해봐야 한다.

문제를 단순하게 만들어서 접근한 뒤에 하나씩 조건을 붙여 해결하는 방법을 지향한다.

누구나 그렇듯이 문제의 조건을 나누어 생각해 보았다.

다음은 내가 처음 생각한 알고리즘이다.

 

알고리즘

1. 백터를 2개 생성해준다. v1은 첫 번째 조건을 만족하는 수를 저장해주는 배열이다. v2는 v1중에서 두 번째 조건을 만족하는 수를 저장해주는 배열이다.
2. 그렇게 조건을 모두 충족시킨 v2배열을 정렬하여 가장 큰 수를 출력해주면 끝이다.

알고리즘은 생각보다 간다하다.

조건 별로 하나씩 따라가 보면 누구나 생각할 수 있는 알고리즘이다.

다음은 코드로 구현 했을 때 이다.

 

망한 코드

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    int cnt=0;
    int a=0;
    
    vector<int>v1(citations.size());
    vector<int>v2(citations.size());
    
    sort(citations.begin(),citations.end());
    
    for(int i=0; i<citations.size();i++){ 
        for(int j=0; j<citations.size();j++){
              citations[j]>=citations[i]?cnt++:false;
        }
        if(cnt==citations[i]){
            v1[i]=cnt;  
        }
        cnt=0;
        
        if((citations.size()-v1[i])<=v1[i]){
            v2[a]=v1[i];
            a++;
        }
    }
   
    sort(v2.begin(),v2.end(),greater<int>());
    answer=v2[0];
    
    return answer;
}

망한 코드이다. 물론 정답도 실패로 뜬다.

테스트 케이스는 모두 잘나오지만 코드를 실행 시켜보면 모두 틀렸다고 나온다.

다시 생각해보자….

잘 생각해보면 논문이 h번 이하 인용되었다는 조건은 H-Index를 결정하는 데 필요하지 않다. 이는 이미 인용 횟수가 h번 이상이 되는 논문을 확인하기 위해 citations 배열이 내림차순으로 정렬되어 있기 때문에 반드시 충족되기 때문이다..

이 코드는 H-Index를 구하기 위해 논문의 인용 횟수를 내림차순으로 정렬한 후에, 인용 횟수가 해당 인덱스보다 크거나 같은 첫 번째 논문의 인용 횟수를 H-Index로 설정한다. 그 후에는 더 이상 H-Index를 증가시킬 수 없는 경우에 반복을 종료하고, 구해진 H-Index를 반환시켜준다.

 

알고리즘

1. 주어진 논문의 인용 횟수를 담은 배열 **citations*를 내림차순으로 정렬한다.
2. 정렬된 배열을 순회하면서 각 논문의 인용 횟수를 확인한다.
3. 현재 인용 횟수가 현재의 인덱스보다 크거나 같은 경우, 즉 **citations[i] >= i + 1*인 경우에는 그 값을 H-Index로 간주한다. 이는 h번 이상 인용된 논문이 h편 이상이라는 조건을 충족시키기 때문이다.
4. 만약 현재 인용 횟수가 현재의 인덱스보다 작다면, 더 이상 H-Index를 증가시킬 수 없으므로 반복을 종료한다.
5. 최종적으로 구해진 H-Index를 반환한다.

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());
    int hIndex = 0;
    
    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] >= i + 1) {
            hIndex = i + 1;
        } else {
            break;
        }
    }
    
    return hIndex;
}

따라서, “if (citations[i] ≥ i+1 )” 조건문을 통해 이미 h번 이상 인용된 논문을 확인할 수 있으며, 그 외의 경우는 더 이상 H-Index를 증가시킬 수 없으므로 반복을 종료하면 된다.

 

if (citations[i] >= i + 1) {
            hIndex = i + 1;

해당 코드 부분은 H-Index를 구하는 핵심적인 부분이다. 이 코드는 citations 배열이 이미 내림차순으로 정렬되어 있음을 이용하여, 해당 인덱스의 값이 그 인덱스 이상의 값들을 포함하고 있는지를 확인한다.

 

이를 이용하여, h번 이상 인용된 논문이 h편 이상인지를 검사한다. citations 배열이 내림차순으로 정렬되어 있기 때문에, 인용 횟수가 h번 이상인 논문은 citations 배열의 앞부분에 위치하게 된다.

 

따라서, **citations[i]**가 현재 인덱스보다 크거나 같은 경우, 즉 **citations[i]**가 i+1 이상이라면, 현재까지 발견된 H-Index를 갱신한다. 이는 h번 이상 인용된 논문이 h편 이상이라는 조건을 충족시키기 때문이다.

예를 들어, citations 배열이 [10, 8, 5, 4, 3]인 경우를 보자.

• 인덱스 0: 인용 횟수 10, 이 경우 h = 1 (10번 이상 인용된 논문이 1편 이상)
• 인덱스 1: 인용 횟수 8, 이 경우 h = 2 (8번 이상 인용된 논문이 2편 이상)
• 인덱스 2: 인용 횟수 5, 이 경우 h = 3 (5번 이상 인용된 논문이 3편 이상)
• 인덱스 3: 인용 횟수 4, 이 경우 h = 4 (4번 이상 인용된 논문이 4편 이상)
• 인덱스 4: 인용 횟수 3, 이 경우 h = 4 (3번 이상 인용된 논문이 4편 이상)

최종적으로 H-Index는 4가 된다.