프로그래머스 - H-Index
https://programmers.co.kr/learn/courses/30/lessons/42747
문제 설명
어떤 과학자의 H-Index 값을 구하려고 한다.
https://en.wikipedia.org/wiki/H-index
위의 위키 내용에 따르면에 따르면, H-Index값 h는 다음 조건을 만족하는 h 값중
최댓값이다.
- 발표한 논문
n편중,h번 이상 인용한 논문이h편 이상이다. - 나머지 논문은
h번 이하로 인용되었다.
어떤 과학자가 발표한 논문의 인용 횟수를 보고, 이 과학자의 H-Index가 몇인지 리턴하자.
제한 사항
- 1 <= 발표한 논문 수 <= 1,000
- 0 <= 논문별 인용 횟수 <= 10,000
1. 반복문 - O(N^2)
문제 설명에서는 조건 중 “나머지 논문은 h번 이하로 인용되었다”
라는 말을 집어 넣었지만, 사실은 별로 신경 쓸 필요가 없는 조건이다.
예제에서 주어진 예시를 보자.
[3,0,6,1,5]
위의 논문 정보를 토대로 얻을 수 있는 H-Index 값은 총 4개이다.
0이 될 수 있다.0번 이상 인용된 논문은[3,0,6,1,5]로 총5편이다.
5는0이상이므로 조건을 만족한다.- 나머지 논문
[]은0번 이하로 인용되었다.
1이 될 수 있다.1번 이상 인용된 논문은[3,6,1,5]로 총4편이다.
4는1이상이므로 조건을 만족한다.- 나머지 논문
[0]은1번 이하로 인용되었다.
2가 될 수 있다.2번 이상 인용된 논문은[3,6,5]로 총3편이다.
3은2이상이므로 조건을 만족한다.- 나머지 논문
[0,1]은2번 이하로 인용되었다.
3이 될 수 있다.3번 이상 인용된 논문은[3,6,5]로 총3편이다.
3은3이상이므로 조건을 만족한다.- 나머지 논문
[0,1]는3번 이하로 인용되었다.
h개의 논문이 h회 이상 인용 되는 논문의 목록에는 h회 이상 인용되는
논문만 들어가게 된다. 그리고 이 기준은 정확히 h개의 논문을 달성할 필요도 없다.
h개 이상이기만 하면 된다.
1회 이상인 논문이 1개 이상 있으면 되고,
10회 이상인 논문이 10개 이상 있으면 된다.
실제로 위키에 들어가면, “나머지 논문은 h회 이하로 인용되었다” 라는 말이 아예 없다.
따라서 우리는 h회 이상 인용된 논문이 h개 이상이 되는 h의 최댓값을 찾으면 된다.
그러면 어떻게 찾아야 할까?
가장 간단하게 생각할 수 있는 방법중 하나는, h의 값을 1씩 증가시키면서
이 논문이 h의 조건을 만족하는지 확인하는 방법이 있다.
하지만 어디까지 찾아야 하는지를 알아야 한다. 따라서, h값은
얼마가 될 지에 대해 생각해야 한다.
H-Index의 계산 방식을 다시 한번 생각해보자.
논문 n편중, h회 이상 인용된 논문이 h개
논문은 총 n편이 주어진다.
그리고 h회 이상 인용된 논문이 h개 라는 조건이 있다.
그러면 다음과 같이 3개의 논문을 가진 과학자가 있다고 치자.
[10000,10000,10000]
3개의 논문의 인용횟수가 모두 10000회이다.
하지만 10000회 이상 인용된 논문을 10000개를 가지고 있는 것은 아니다.
논문의 개수는 총 3개이므로, 4회 이상 인용된 논문이 4개라는 조건도
만족시킬 수 없다.
즉, H-Index의 최대값은 발표한 논문의 수와 일치한다.
총 3개의 논문을 발표했다면, 가능한 H-Index의 최댓값은 3이다.
발표한 논문들이 아무리 인용이 되었어도 3이다.
그러면 어디까지 순회를 해야 할 지 정해졌다.
1에 대해서 H-Index 값을 만족하는지 확인하고,
2에 대해서 H-Index 값을 만족하는지 확인하고,
…
n에 대해서 H-Index 값을 만족하는지 확인한다.
위의 값 중 최댓값을 리턴하면 H-Index 값을 구할 수 있을 것이다.
하지만, 순회를 반대로 한다면 어떨까?
n부터 순회해서, 1까지 H-Index 값을 만족하는지 찾아보는 것이다.
만약 순회하는 도중에 H-Index값을 만족하는 값을 찾았다면, 그 값이 최댓값이다. 따라서 그 밑의 값은 더 이상 순회할 필요가 없다. 그 아래 값들이 H-Index를 만족하는 값이라고 하더라도, 절대 최댓값이 될 수없다.
따랴서 크기가 큰 n부터 시작해서, 1까지 순회하는 코드를 작성해보자.
solution_loop.cpp
#include <vector>
using namespace std;
int solution(vector<int> citations) {
int answer = 0, size = static_cast<int>(citations.size());
for (int i=size-1;i>=0;--i)
{
int larger = 0;
for (int j=0;j<size;++j)
{
if (citations[j] >= (i+1))
++larger;
}
if (larger >= (i+1))
return i+1;
}
return 0;
}
2. 정렬 - O(NlogN)
위의 반복문으로도 풀 수 있지만, 이 문제의 카테고리는 정렬이다. 정렬로는 어떻게 풀어야 할까?
예제로 주어진 값을 한 번 정렬해보자.
[0,1,3,5,6]
이렇게 정렬된 정보를 가지고 어떻게 H-Index 값을 찾을까?
위의 H-Index값이 1을 만족하는지 확인하는 방법부터 생각해보자.
1을 만족시키려면, 1이상 인용된 논문이 1개 이상 있어야 한다.
인용 횟수 1이상인 논문 1개만 찾으면 되므로, 가장 많이 인용된 논문 하나만 찾아보면
된다.
그러면 정렬된 배열에서 가장 많이 인용된 논문은 어디에 위치하고 있을까?
위의 예시처럼 오름차순으로 정렬을 했다면, 맨 뒤에 위치하고 있을 것이다.
가장 많이 인용된 논문의 인용 횟수가 1 이상이라면, H-Index 값은 1을
만족한다. 따라서 맨 뒤에 위치한 논문 인용횟수 하나만 확인하면 된다.
그러면 이번엔 2를 만족하는지 확인하는 방법에 대해 생각해보자.
이번엔 인용 횟수가 2이상인 논문 2개를 찾아야 한다. 그러면 끝에서부터 하나씩
논문 인용횟수가 2이상인지 찾아봐야 할까?
아니다. 뒤에서 2번째에 위치한 논문이 2회 이상 인용되었는지에 대해서만 확인하면 된다.
만약에 뒤에서 2번째에 위치한 논문이 2이상이라면, 그 뒤에 있는 논문도
2회 이상 인용된 논문이다. 오름차순으로 정렬되어 있기 때문이다.
그러면 뒤에서 2번째에 위치한 논문이 2미만이라면?
그러면 남은 논문은 1개이므로, 뒤의 논문의 인용횟수가 아무리 많아도
H-Index값 2를 만족시킬 수 없다. 하나 빼고 모두가 인용횟수가 2 미만이기
때문이다.
이를 일반화 시키면 다음과 같이 정리할 수 있다.
오름차순으로 정렬된 논문 인용횟수 배열에 대해서, 뒤에서 h번째 논문이 h회 이상 인용되었는지에 대해 확인하면, H-Index값 h를 만족하는지 확인할 수 있다.
그러면 이 과정을 코드로 작성해보자.
solution_sort.cpp
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> citations) {
sort(citations.begin(), citations.end());
int size = static_cast<int>(citations.size());
for (int i=size-1;i>=0;--i)
{
if (citations[size-1-i] >= i+1)
return i+1;
}
return 0;
}
내림차순으로 정렬하면 순서를 반대로 하면 된다.
정렬한 후 h값을 찾는 과정을 이진 탐색을 사용할 수도 있다. 그러면 탐색하는데 소요되는 시간은 O(LogN)이 될 것이다. leetcode의 H-Index II 문제에서 풀어볼 수 있다.
3. Counting Sort - O(N)
정렬 중에는 Counting Sort라는 특수한 형태의 정렬이 있다. 아래의 예제를 통해 어떻게 동작하는지 확인해보자.
[5,1,3,9,5,4,4,8,1]
위의 배열에서 최댓값은 9다.
그러면 9+1 크기 만큼의 배열을 하나 만들어준다.
[0,0,0,0,0,0,0,0,0,0]
그리고 정렬되지 않은 배열을 차례대로 순회해보자.
맨 처음에 만난 숫자는 5다.
새로 생성한 배열의 인덱스 5에 해당하는 곳에 1을 더해주자.
[0,0,0,0,0,1,0,0,0,0]
다음에 만난 숫자는 1이다.
새로 생성한 배열의 인덱스 1에 해당하는 곳에 에 1을 더해주자.
…
이 과정을 끝까지 반복하면 새로 생성한 배열의 정보는 다음과 같다.
[0,2,0,1,2,2,0,0,1,1]
이렇게 해서 배열에 포함된 숫자의 개수를 가지고 있는 배열을 생성했다.
위의 배열을 통해, 1은 2개가 있고, 3은 1개가 있다는 정보를 알 수 있다.
이제 새로 생성된 배열을 쭉 순회하면서, 각 숫자에 대응하는 번호를
해당 배열에 들어있는 숫자 만큼 출력하면, 원본 배열을 정렬한 효과를 얻을 수 있다.
출력은 stdout에 할 수도 있고, 또 다른 배열에 복사 할 수도 있고, 원본을 보존할 필요가 없다면 원본 배열을 덮어씌워도 된다.
이렇게하면 O(N+k)의 시간복잡도로 정렬을 수행할 수 있다.
k는 해당 배열에 존재하는 최댓값을 의미한다.
Counting Sort는 최댓값 k가 작으면 작을수록 크게 효과를 볼 수 있는 정렬이다.
하지만 k가 크면 다른 정렬보다 성능이 나빠진다.
그리고 데이터의 종류가 정수가 아니면 쓰기 어렵다.
따라서 제한적인 상황에만 쓸 수 있는 정렬인데, 마침이 문제가 그 제한적인 상황이다.
이 문제에서 k는 곧 n으로 고정해도 상관이 없다.
H-Index값 h의 최댓값은 n이기 때문이다.
굳이 배열을 한 번 순회하면서 최댓값 k를 찿으려 할 필요가 없다.
k의 최댓값은 n이지만, 참조된 횟수의 최댓값은 10,000이다.
만약 인용 횟수 배열을 순회하던 중, n의 값을 넘는 수를 만나면 어떻게 해야 할 까?
최댓값이 10,000이니까 배열을 항상 10,001개를 만들어야 할 까?
그럴 필요는 없다. n을 넘는 값을 만나는 경우,
그냥 n을 참조하는 인덱스에 1을 더해주면 된다.
H-Index 값은 n을 넘을 수 없다는 특성 상,
논문이 n개 있으면 n+1회 이상 인용된 논문이 아무리 많아봤자
해당 논문들이 n회 인용된 것과 효과가 같다.
[3,3,3] 의 H-Index도 3이고,
[10000,10000,10000]의 H-Index도 3이다.
따라서, n을 넘어가는 인용 횟수는 n회 인용된 셈 치고 넘어가도
H-Index를 구하는데 아무런 문제가 없다.
이제 이 정보를 토대로 H-Index를 구해야 한다.
H-Index를 구할 때는 굳이 각 숫자의 등장 횟수를 다른 배열로
출력하지 않아도 된다. 우리에게 필요한 것은 각 숫자의 등장 횟수이다.
그러면 예제를 Counting Sort로 풀어보자.
예제의 숫자 별 등장 횟수를 모아놓은 배열은 다음과 같다.
[1,1,0,1,0,2]
배열의 맨 뒤의 값은 5회 이상 참조된 논문의 수를 의미한다.
5회 이상 참조된 논문의 수는 2다.
이 값은 5 미만이므로 H-Index가 될 수 없다.
4회 이상 참조된 논문의 수는 0+2다.
4회 참조된 논문의 수는 0이고,
5회 이상 참조된 논문의 수는 2다.
이 값은 4 미만이므로, H-Index가 될 수 없다.
3회 이상 참조된 논문의 수는 1+0+2다.
3회 참조된 논문의 수는 1이고,
4회 참조된 논문의 수는 0이고,
5회 이상 참조된 논문의 수는 2다.
이 값은 3이상이므로, H-Index가 될 수 있다.
따라서 H-Index 값은 3이다.
위의 과정을 통해 H-Index 값을 도출하는 방법을 알 수 있다.
- 인용 횟수
n인 논문의 수 부터1인 논문의 수를 차례대로 더해나간다. i번째 까지 더했을 때, 총 인용 횟수가i이상이라면i를 리턴한다.
위의 과정을 코드로 표현해보자.
solution_counting_sort.cpp
#include <vector>
using namespace std;
int solution(vector<int> citations) {
int size = static_cast<int>(citations.size());
vector<int> counts(size+1, 0);
for (int v : citations)
++counts[min(v,size)];
int papers = 0;
for (int i=size;i>0;--i)
{
papers += counts[i];
if (papers >= i)
return i;
}
return 0;
}
Counting Sort를 활용할 일은 그렇게 많진 않다.
하지만 알고 있으면 가끔씩은 유용하게 사용할 수 있다.
억지로 기억할 필요는 없지만, 알아두면 좋다.
Comments