[프로그래머스 Level 2] [정렬] H-Index (C++)

마지막 정렬 문제를 들고 왔습니다.

분명 정렬은 개념자체가 어렵지 않기 때문에 맞추고 넘어가야 하는데 꼭 맞춰야 한다는 부담감이 오히려 역으로 어렵게 만들기도 한다는 것을 느꼈습니다.

문제를 너무 어렵게 이해했어요 ㅋㅋㅋㅋㅋ

출처 : 프로그래머스 코딩테스트 연습 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표

programmers.co.kr

0. 문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

0.0. 제한사항

과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

0.1. 입출력 예

citations	return
[3, 0, 6, 1, 5]	3

0.2. 입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

1. 풀이 과정

h는 citations의 수까지 가능하기 때문에, 모든 h를 돌려서 조건에 맞는 친구들(citation[i]가 h보다 큰 친구들의 수)을 센 후에 마지막에 h랑 비교해서 answer에 넣는 방식으로 만들었습니다.

for문이 두번 돌았기 때문에 Big-O notation은 O(n^2)가 되겠네요. while문을 사용해도 동시에 만들 수 있을 것 같습니다. 지금 글을 작성하면서 생각해 본건데, 보다 효율적으로 만든다면 h를 큰 수부터 줄어들게 한 다음 만족하는 경우 바로 break으로 빠져나가게 할 수도 있을 것 같습니다.

2. 소스 코드

2.0. 최초 통과 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    int size = citations.size();
    
    // 가능한 h들을 싸그리 모아서, 그 중 최댓값을 answer에 넣기
    for (int h = 0; h <= size; ++h){
        int cnt = 0; // h번 이상 인용된 논문의 수
        for (int i = 0; i < size; ++i){
            if(h <= citations[i])
                ++cnt;
        }
        if(h <= cnt)
            answer = h;
    }
    return answer;
}

2.1. h를 뒤에서부터 세기

굉장히 유의미한 발전이 있었습니다. 극악의 케이스 (전부 같은 citations를 가졌다든지..)를 제외한다면 무조건 size만큼 돌아야 하는 위의 코드와는 달리 꽤 큰 차이로 빠르게 종료할 수 있습니다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    int size = citations.size();
    
    // 가능한 h들을 싸그리 모아서, 그 중 최댓값을 answer에 넣기
    for (int h = size; h >= 0; --h){
        int cnt = 0; // h번 이상 인용된 논문의 수
        for (int i = 0; i < size; ++i){
            if(h <= citations[i])
                ++cnt;
        }
        if(h <= cnt){
            answer = h;
            break;
        }
    }
    return answer;
}

3. 후기

다 풀고 나서 바꾼 코드가 시간적으로 엄청난 이득을 가져다줘서 놀랐습니다. 이래서 한번 돌아가게 만든 코드도 다시 돌아보는 과정이 필요한 것 같습니다. 정렬문제는 알고리즘을 생각하는게 어렵긴 한데 풀 때는 꽤 재밌게 풀 수 있는 것 같아서 마음에 듭니다 :)

저작자표시

[프로그래머스 Level 2] [정렬] H-Index (C++)