[ 프로그래머스 H-Index (Lv2) ] (C++)

프로그래머스의 H-Index(Lv2) 문제이다.

 

[ 문제풀이 ]

한 과학자가 발표한 논문의 인용 횟수가 주어질 때, H-Index의 값을 구해야 하는 문제이다.

정말 간단한 문제인 것 같았는데, 문제를 완벽하게 이해하지 못해서 생각보다 시간이 꽤 걸렸었던 문제이다.

문제를 다시한번 확인하는 과정부터 정답을 도출하는 과정까지 진행해보자.

 

#1. H-Index ?

(※ 이 부분은 문제를 이해하기 위해서 적는 부분입니다. 만약, 문제를 완벽하게 이해하신 분이라면 #1의 과정을 읽지 않고

#2의 과정으로 바로 넘어가셔도 무관합니다. ※ )

 

H-Index에 대해서 다시한번 확인해보고 본격적인 문제 풀이에 들어가보자.

문제에 나와있는 H-Index의 정의는 다음과 같다.

"N편 중, H번 이상 인용된 논문이 H편 이상이고, 나머지 논문이 H번 이하 인용되었다면 H의 최댓값이 이 과학자의 H-Index이다"

그럼 간단한 예시를 한 가지 들어보자.

Citations = [ 3 , 5 , 2 , 4 , 1 ] 이라는 예시를 생각해보자.

이 예시의 원소 하나하나가 무슨 의미를 가지는지부터 다시한번 정리해보자.

가장 첫번째 논문부터 임의적으로 'A' , 'B' , 'C' , 'D' , 'E' 라고 이름 붙여 보자. 그럼 다음과 같이 표현할 수 있다.

논문 A의 인용횟수는 3회입니다.

논문 B의 인용횟수는 5회입니다.

논문 C의 인용횟수는 2회입니다.

논문 D의 인용횟수는 4회입니다.

논문 E의 인용횟수는 1회입니다.

여기서의 H-Index의 값을 구해보자.

 

먼저, H-Index = 1 이라고 가정해보자.

즉 ! 5개의 논문 중에서, 1번 이상 인용된 논문이 1편 이상이고, 나머지 논문이 1번 이하 인용되었다면 이는 H-Index의 후보가 될 수 있다. 후보라고 표현하는 이유는 우리는 이 H-Index값 중에서의 최댓값을 구해야 하기 때문이다.

1번 이상 인용된 논문은 A, B, C, D, E 5개가 된다. 이후, 나머지 논문은 더 이상 없게 된다. 따라서, H-Index로 '1'이라는 값은 후보가 될 수 있다. 조건에 위배되는 사항이 없기 때문이다.

 

H-Index = 2 라고 가정해보자.

5개의 논문 중에서, 2번 이상 인용된 논문이 2편 이상이고, 나머지 논문이 2번 이하 인용되었는지 확인을 해보면 된다.

2번 이상 인용된 논문은 A, B, C, D 로 총 4편이 된다.

즉 ! 2번 이상 인용된 논문은 총 4편으로 2편 이상이라는 조건을 만족하게 된다.

그리고 나머지 논문, 즉, 논문 E의 인용횟수가 2번 이하인지 체크해보면 E의 인용횟수는 '1'로 2번 이하라는 것을 확인할 수 있다.

따라서 , H-Index의 후보로 '2'라는 값도 적절하다.

 

H-Index = 3 이라고 가정해보자.

5개의 논문 중에서, 3번 이상 인용된 논문이 3편 이상이고, 나머지 논문이 3번 이하로 인용되었는지 확인을 해보면 된다.

3번 이상 인용된 논문은 A , B , D 로 총 3편이 된다.

즉 ! 3번 이상 인용된 논문은 총 3편으로 3편 이상이여야 한다는 조건을 만족하게 된다.

그리고 나머지 논문, 즉, C와 E의 인용횟수를 체크해보면, 각각 2번, 1번으로 3번 이하로 인용되었다.

따라서, H-Index의 후보로 '3'이라는 값도 적절하다.

 

H-Index = 4 라고 가정해보자.

5개의 논문 중에서, 4번 이상 인용된 논문이 4편 이상이고, 나머지 논문이 4번 이하로 인용되었는지 확인을 해보면 된다.

4번 이상 인용된 논문은 B , D로 총 2편이 된다.

여기서 보면 4번 이상 이용된 논문이 4편 이상이 되질 않기 때문에 '4'는 적절한 H-Index의 후보값이 아니다.

H-Index = 5 인 경우에도 마찬가지로 조건에 위배되어 진다. 따라서 H-Index의 최댓값은 '3'이 된다.

 

이런식으로 구하는 것이 H-Index이다. 정말 간단한 한 가지 예시만 더 확인을 해보자.

다른 분이 올려주신 예시였는데 너무 좋은 예시라고 생각한다.

Citations = [ 88 , 89 ]

H-Index의 값은 얼마일까 ???

H-Index의 값은 '2'이다. 왜 그럴까 ??

H-Index = 2로 생각하고 위의 예시를 풀어 적어보면 다음과 같다.

"논문 2편 중에서 2번 이상 인용된 논문이 2편 이상이고 나머지 논문이 2번 이하로 인용되었다면, H-Index의 값은 2입니다" 가 되는 것인데, '88'번 인용된 논문도 2번 이상 인용된 논문에 해당하고, '89'번 이용된 논문도 2번 이상 인용된 논문에 해당하므로, 2번 이상 인용된 논문이 2편 이상이라는 조건을 만족하게 된다. 나머지 논문은 더 이상 존재하질 않는다. 따라서 위의 답은 '2'이다.

왜 답이 88 or 89가 아닐까 ??

'88'을 대입해보자. H-Index = 88 이라고 생각을 해보자.

그럼 이는, "논문 2편 중에서 88번 이상 인용된 논문이 88편 이상이고 나머지 논문이 88번 이하로 인용되었는가?" 를 판단해보면 된다. 88번 이상 인용된 논문은 2편밖에 없다. 88편이 애초에 존재하질 않는다. 따라서, 정답이 88 or 89는 절대 될 수가 없다.

즉 ! 우리가 찾는 정답은, "주어진 배열속에 존재하는 값이 아니다" 라는 것을 알 수 있다.

 

#2. 정답 도출

문제를 이해하는게 어렵지 실제로 계산하는 과정은 너무나도 간단해서 여러개로 쪼개기 애매해서 바로 정답을 도출하는 과정에서 모든 풀이과정을 알아보자.

본인은 가장 먼저 주어진 배열을 "오름차순으로 정렬" 을 시켜 주었다. 과연, 여기서 정렬이 무슨 의미를 가지게 될까 ??

여기서의 정렬이 무슨 의미를 갖는지는 밑에서 이야기 해보도록 하자. 그 전에 정렬의 특징을 한 가지 살펴보자.

오름차순으로 정렬을 하면 다음과 같은 특징이 하나 있다.

"특정 Index 이후에 나오는 값들은, 해당 Index의 값보다 최소한 같거나 크다."

너무나도 당연한 이야기이다. [ 3 , 5 , 2 , 4 , 1 ] 을 오름차순으로 정렬하게 되면 [ 1 , 2 , 3 , 4 , 5 ] 가 되는데 여기서 1번 Index에 해당하는 값은 '2'이다. 그리고 그 이후에 나오는 값들은 최소 '2'보다 크거나 같다. 너무나도 당연한 이야기이다.

 

그럼, [ 3 , 5 , 2 , 4 , 1 ] 이라는 예시가 주어졌다고 가정하고 이를 왜 정렬을 시키는지는 모르겠지만 일단 정렬을 시킨 것으로 한번 진행을 해보자. 오름차순으로 정렬을 하게 되면, [ 1 , 2 , 3 , 4 , 5 ] 가 될 것이다.

그리고, H-Index의 정의를 다시한번 살펴보자.

"N편의 논문들 중에서, H번 이상 인용된 논문이 H편 이상이여야 합니다. 그리고 나머지 논문은 H번 이하 인용되어야 합니다. 이를 만족시키는 H값들 중, 최댓값이 H-Index입니다."

우리는 지금부터 H-Index의 정의를 2부분으로 나누어서 진행을 해볼 것이다.

"N편의 논문들 중에서, H번 이상 인용된 논문이 H편 이상이여야 합니다. 그리고 나머지 논문은 H번 이하 인용되어야 합니다. 이를 만족시키는 H값들 중, 최댓값이 H-Index입니다."

H-Index의 정의에서 빨강색으로 표시된 저 조건을 2개로 나눠볼 것이다. 조금은 이상할 수 있지만 다음과 같이 2개로 나눌 수가 있다.

1. 특정 논문이 H번 이상 인용되었는가 ?

2. 논문의 갯수가 H편 이상을 만족할 수 있는가 ?

조금은 억지스럽지만 위의 2가지로 나눠서 진행을 해볼 것이다.

 

먼저, 2번조건부터 진행을 할 것이다. "논문의 갯수가 H편 이상을 만족할 수 있는가 ?!"

우리는 이를 배열 혹은 Vector의 Index번호만으로 알아낼 수 있다.

주어진 배열의 크기는 '5' (N = 5) 라고 가정해보자.

그리고 0번 Index를 탐색하고 있다고 가정해보자.

현재 Index를 포함해서, 남은 논문의 갯수는 5개가 될 것이다.

1번 Index를 탐색하고 있다고 가정해보자.

현재 Index를 포함해서, 남은 논문의 갯수는 4개가 될 것이다.

1번 Index를 탐색하더라도, 남은 논문은 0 , 2 , 3 , 4 번 Index에 해당하는 논문들과, 현재 Index인 1번 Index를 포함해서 총 5개가 되지 않나 ?! 라고 할 수 있지만, 우리는 이미 지나간 Index에 대해서는 계산을 하지 않을 것이다. 그리고 그러기 위해서 오름차순으로 정렬을 한 것이다. 이 부분은 아래쪽에서 더욱 구체적으로 이야기 할 것이다.

즉 ! K번 Index를 탐색하게되면, 현재 Index를 포함해서 남은 논문의 갯수는 N - K 개가 된다는 것을 알 수 있다.

우리는 이 값을 통해서, "논문의 갯수가 H편 이상을 만족할 수 있는가?" 를 알아낼 수 있다.

 

두 번째로, 1번 조건인 "특정 논문이 H번 이상 인용되었는가?" 를 알아볼 것이다.

이는, Index 번호가 아닌 해당 Index가 가지고 있는 값을 통해서 알아낼 수 있다.

[ 1 , 2 , 3 , 4 , 5 ] 로 시작을 해보자.

가장 먼저 0번 Index를 살펴보자. 위에서 했던 이야기를 토대로, 현재 Index포함해서 남은 논문의 갯수는 5 - 0 = 5개가 된다는 것을 알 수 있다. 즉 ! 우리는 0번 Index를 계산할 때, H-Index 의 값으로 '5'가 적절한지? 를 판단할 수 있다.

왜냐하면, 결국 H-Index는 H번 이상 인용된 논문이 H편 이상이여야 한다. 즉 ! 몇 번 인용되었는지는 둘째 치고, 카운트 할 수 있는 논문의 갯수가 H편 이상이여야 하는데 이를 만족하는 최댓값이 '5'이기 때문이다.

그렇다면, 특정 논문이 5번 이상 인용되었는가? 를 판단해야 하는데, 0번 Index가 가지고 있는 값은 '1'이다. 따라서, 5번 이상 인용될 수가 없다. 왜그럴까 ?! 극단적으로 예를들어서 1번 ~ 4번 Index가 모두 1000 이라는 값을 가지고 있다고 가정해보자. 하지만, 0번 Index가 5번 이상 인용되지 않았기 때문에 절대로 5편 이상 인용되었다고 말을 할 수가 없다.

따라서, citations[0] 의 값을 통해서 "특정 논문이 H번 이상 인용되었는지" 를 판단할 수 있다.

 

1번 Index로 넘어가보자.

현재 Index를 포함해서 남은 논문의 갯수는 5 - 1 = 4개가 된다는 것을 알 수가 있다.

즉 ! H-Index의 값으로 '4'가 적절한지? 를 판단해볼 것이다.

citations[1] = 2 로써, '4'보다 작은 값을 가지게 된다. 즉 ! 4번 이상 인용된 논문이 4편 이상이 아닙니다 라는 결론을 낼 수 있고 이는 H-Index의 값으로 적절하지 않다. 왜 ?! citations[0] 이 만약에 4보다 더 큰 값이였다면 위의 조건을 만족할 수도 있지 않을까 ??

예를 들어서 이런 경우이다. [ 100 , 2 , 5 , 6 , 7 ] 이라고 주어졌다면, 4번 이상 인용된 논문이 4편 이상이 되는 것이 아닐까 ??

우리가 정렬을 한 이유가 여기서 드러난다. 또한, 이미 지나간 Index에 대해서는 계산을 하지 않는다는 이유도 여기서 드러나게 된다. 나보다 더 작은 Index에 속하는 데이터들은 나보다 최대 같거나 작다는 것이 정렬을 통해서 자명해졌기 떄문이다.

 

2번 Index로 넘어가보자.

현재 Index를 포함해서 남은 논문의 갯수는 5 - 2 = 3 개가 된다.

즉 ! H-Index의 값으로 '3'이 적절한지? 를 판단해볼 것이다.

citations[2] = 3 으로써, 3과 같은 값을 가지게 된다. 즉 ! 3 이상에 해당하는 숫자이다.

그래서 정답은 '3'이다.

무슨말일까 ?! 왜 갑자기 정답이 3이될까 ?? 3번 이상 인용된 논문이 3편이 안될수도 있지 않나 ? 정말 우연히 2번 Index에 해당하는 값만 3이상이고 나머지는 아닐수도 있잖아 ?! 여기서 위에서 이야기했던 너무나도 당연했던 정렬의 특징이 나타난다.

"특정 Index 이후에 나오는 값들은, 해당 Index의 값보다 최소한 같거나 크다."

이 이후에 나오는 값들은 최소 3이상이다. 이 문제에 맞게 이야기해보자면, 이 이후에 나오는 논문들의 인용횟수는 최소 3회 이상이라는 것이다. 극단적으로 3번, 4번 Index가 모두 [ 3 , 3 ] 이라고 가정하더라도, 3번 이상 인용된 논문이 3편 이상이 된다.

그렇다면, H-Index 값의 후보로 '3'이 들어가는 것 까지는 알겠는데 이게 왜 정답이 될까 ???

눈치를 챘을 수 있지만, Index번호가 커지면 커질수록 H-Index의 값은 줄어들게 된다. 왜 ?? 계산할 수 있는 남은 논문의 갯수가 줄어들기 때문이다. N - K 에서 K의 값이 계속해서 커지고 있는 꼴이다. K의 값이 커지면 커질수록 N - K의 값은 작아지는 것이 당연하다.

그 중에서 우리는 최댓값을 찾아야 하기 때문에 위의 조건을 만족하는 '3'이 바로 정답이라는 것을 알 수 있다.

 

한 가지 예를 더 들어보자. [ 200 , 300 , 400 , 100 , 500 ] 이 있다. 오름차순으로 정렬해보면 [ 100 , 200 , 300 , 400 , 500 ]

0번 Index부터 탐색을 해보자. 0번 Index를 탐색함으로써 우리는 계산할 수 있는 남은 논문의 갯수가 5 - 0 = 5 개라는 것을 알 수 있다.

H-Index로 '5'라는 값은 적절할까 ?? 즉 ! 5번 이상 인용된 논문이 5편 이상이 될까 ??

citations[0] = 100 으로 5보다 크다. 즉 ! 5번 이상 인용된 논문이다 .그래서 정답은 5이다.

왜 ?? 0번 Index 이후에 나오는 모든 값들은 최소 '100'보다 크다는 것이 자명한 사실이다. 정렬을 했기 때문에 !

그리고 그 이후에 탐색을 계속하더라도, H-Index의 값은 점점 더 작아진다고 했다.

그렇기 때문에 최댓값은 '5'가 되는 것이다.

 

되게 어려워보이고 복잡해 보이지만 코드를 보면 놀랄정도로 너무나도 간단한 문제이다...

본인도 문제를 이해하는데 조금 시간이 걸렸었던 문제이고 이해한 내용을 코드로 설명하는 것보다 말로 설명하는 것이 훨씬 더 어려웠던 그런 문제인 것 같다..

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> citations) 
{
    int answer = 0;
    sort(citations.begin(), citations.end());
    for(int i = 0 ; i < citations.size(); i++)
    {
        int H_Index = citations.size() - i;
        if(citations[i] >= H_Index) return H_Index;
    }
    return answer;
}