본 문제는 문제를 이해하는 데에 무척 오려 걸렸다. 문제를 이해한 후에도 나름의 알고리즘을 세우고 코드를 짰지만 도무지 어느 곳이 잘못된지를 몰라 애를 많이 먹어서 알고리즘을 한 번 뒤엎었던 문제이기도 하다. 처음에 생각했던 알고리즘과 다른 알고리즘으로 문제를 해결한 후에 다른 사람의 코드를 보며 처음 세웠던 알고리즘을 정리해 다시 짜면서 해결코드가 두 가지가 되었는데, 코드를 보면서 알고리즘이 어떻게 다른지 생각해보는 것도 좋은 공부가 될 것 같다 :)
1. 문제
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다.
어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다.
위키백과에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.
제한조건
- 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
- 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
2. 알고리즘! 생각해보자
뒤엎은 알고리즘으로 해결한 코드 (통과 O)
citations 벡터를 내림차순으로 정렬한다.citations 의 원소를 반복하며 논문의 인용 횟수와 인용된 논문의 갯수 중 작은 값,
그리고 이 값과 지금까지의 가장 큰 H-Index 중 큰 값을 H-Index의 값으로 설정한다.
(논문 인용 횟수 = citations[i], 논문 갯수 = citations.size()-i, 현재의 가장 큰 H-Index = h_index)citations 벡터의 반복이 끝나면 H-Index 값을 반환한다.
해결 후 다른 사람 코드를 참고해 수정한 코드 (통과 O)
citations 벡터를 내림차순으로 정렬한다.citations 의 원소를 반복하다가 논문의 갯수가 논문의 인용 횟수보다 커지는 순간 논문의 갯수 - 1 값을 반환한다.
(H-Index는 어차피 h번 이상 인용된 논문이 h편 이상일 때 최대 h 값이다. 논문의 인용 횟수보다 논문의 갯수가 커지는 순간 H-Index를 만족 못하기 때문에 해당 값 - 1을 반환 → 이전 값 까지는 만족 했으니까)
3. 해결코드
[C++]
초반 알고리즘으로 생각했던 코드 (통과X)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> citations) {
sort(citations.begin(), citations.end());
for (int i = 0; i < citations.size(); i++) {
if (i + 1 >= citations[i])
return min(i+1, citations[i]);
return citations.size();
}
|
뒤엎은 알고리즘으로 해결한 코드 (통과 O)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> citations) {
sort(citations.begin(), citations.end(), greater<int>());
for (int i = 0; i < citations.size(); i++) {
h_index = max(h_index, min(citations.size() - i, citations[i]));
}
return h_index;
}
|
해결 후 다른 사람 코드를 참고해 수정한 코드 (통과 O)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> citations) {
sort(citations.begin(), citations.end(), greater<int>());
for (int i = 0; i < citations.size(); i++)
if (i + 1 > citations[i])
return i;
return citations.size();
}
|
4. 해결능력UP, 깊이 생각해보기
- 초반에 생각했던 알고리즘이 전체적으로는 맞았지만 놓치고 있는 부분이 조금 있었다
혹시 나와 같이 생각했다면 테스트 케이스 ‘[20, 19, 18, 1]’의 경우를 고려해보길 바란다 - 다른 사람 코드를 참고해 수정한 코드에서는 H-Index가 해당 논문의 인용횟수/인용된 논문의 수와 다를 경우를 보장
vector를 내림차 순으로 sorting하는 법- max값, min값 구하는 법
5. 참고해서 문제해결 ٩( ᐛ )و
1
| 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
|
