프로그래머스-H-Index

목차

1.문제

2.문제풀이과정

3.타인의 코드 분석

 

1.문제

2.문제풀이과정

2-1. 문제 요구사항

• 논문의 인용 횟수를 담은 배열 citations (1편 이상 1,000편 이하)
• 출력은 조건을 만족하는 H-Index의 최댓값 (int)
• 핵심 조건은 h편 이상의 논문이 각각 h번 이상 인용이되어야 하고 나머지 논문은 각각 h번 이하 인용이 되어야합니다.

2-2. 문제의 풀이과정

 

처음에 이 문제를 봤을때 이해가 안되어서 한동안 고민을 했었습니다. 문제를 읽었을때 요구하는 h가 논문 편수인지 아니면 인용횟수인지를 알아내는데에 시간이 조금을 걸렸었지만 내가 이해를 한 내용은 이러했습니다.

 

1. 논문 인용 횟수를 내림차순으로 정렬을 한다. 

2. 앞에서부터 차례대로 보면서 "논문의 개수" 와  "인용 횟수"를 비교를 한다.

3.인용 횟수가 논문 개수보다 크거나 작거나, 처음으로 인용 횟수가 논문 개수보다 작아지는 순간이 바로 문제에서 요구를 하는 H-Index.

 

 

2-3. 문제 의사코드

 

위의 풀이 과정을 토대로 해서 제가 구상한 의사코드는 아래와 같습니다. 

1. 논문의 내림차순으로 정렬하기
-> Arrays.sort를 써서 오름차순으로 정렬하기.
-> 논문의 배열을 돌리면서 내부에서 인덱스를 스왑해서 정렬하기.

2.반복문을 돌리면서 i가 인용횟수를 넘으면 break 아니면 answer를 올린다.

3.return을 answer로 한다.

 

그리고 해당 의사코드를 토대로 작성한 코드는 아래와 같습니다.

3.타인의 코드 분석

코드를 제출후에 다른 사람들이 제출한 코드를 보았는데 다양한 풀이를 한 사람들이 많았습니다.  그중에서 인상에 남았던 방식은 다음과 같습니다.

• 정렬을 활용한 방법
• 누적합
• 병합정렬을 활용한 방법
• 우선순위 큐를  활용한 방법
• 완전탐색을 활용한 방법

3-1.정렬을 활용한 방법

 

이 코드의 경우에는 오름차순 정렬된 배열을 뒤에서부터 순회하며, 인용 횟수(citations[i])와 남은 논문의 개수(citations.length - i) 중 최솟값(min)을 구합니다. 이 중 가장 큰 값을 갱신하여 H-Index를 도출합니다.  

 

장점: 코드가 매우 짧은 편이라는 점입니다. 

단점: H-Index의 정의를 직관적으로 이해한 상태에서 수학적으로 압축된 코드라, 처음 코드를 볼 때 직관성이 떨어질 수 있습니다.

 

3-2. 누적합을 이용한 방법

 

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        answer = getHIdx(citations);
        return answer;
    }

    public int getHIdx(int[] citations)
    {
        int[] s = new int[citations.length + 1];
        for (int i = 0; i < citations.length; i++) s[Math.min(citations.length, citations[i])]++;

        int sum = 0;
        for (int i = s.length - 1; i >= 0; i--)
        {
            sum += s[i];
            if (sum >= i)
                return i;
        }

        return 0;
    }
}

 

 

이 방식은 전체 배열을 정렬하는 대신, 빈도 배열(s)을 이용해 각 인용 횟수가 몇 번 등장하는지 기록을 하는 방식입니다. 이후 뒤에서부터 누적 합(sum)을 구해가며  "누적 논문 수 ≥ 인용 횟수" 조건을 만족하는 첫 순간의 인덱스를 반환합니다.

 

장점: 정렬을 생략하기 때문에 데이터의 크기가 클 경우 시간 복잡도 면에서 더 유리할 수 있습니다.

단점: 빈도 저장을 위한 추가적인 배열 메모리가 소모됩니다.

 

3-3.병합정렬을  활용한 방법

 

 

Arrays.sort를 쓰지 않고, 분할 정복 기반의 병합 정렬 로직을 직접 구현(mergesort, merge)하여 배열을 정렬한 뒤 탐색합니다.

장점: 라이브러리 의존성을 제거하고 순수 정렬 알고리즘의 동작 원리를 바닥부터 구현해 보며 깊이 있는 이해를 얻을 수 있습니다.

단점: 코드가 불필요하게 길어지고 복잡해지며, 실무나 코딩 테스트 시험 환경에서는 시간 낭비가 될 수 있습니다.

 

3-4.우선순위 큐를 활용한 방법

 

 

모든 원소를 최대 힙에 넣어 내림차순 상태를 유지하게 만듭니다. answer를 1씩 늘려가며 큐의 최상단 값(peek())과 비교해 조건을 만족할 때마다 요소를 꺼냅니다(poll()).

장점: 자료구조의 특성을 살려 H-Index의 정의("h번 이상 인용된 논문이 h편 이상")를 순차적 시뮬레이션 형태로 명확하게 표현했습니다.

단점: 단순 배열 정렬에 비해 힙 삽입/삭제 연산에 따른 오버헤드가 더 큽니다.

 

 

3-5.완전탐색을 활용한 방법

 

 

가능한 H-Index 후보값들을 내림차순으로 전부 대입하며, 매번 전체 배열을 순회해 조건을 만족하는지 직접 검증합니다.

장점: 문제의 정의를 머릿속에 떠오르는 그대로 직관적으로 코드로 옮겼기 때문에 가독성과 이해도가 가장 높습니다.

단점: 완전탐색이다보니깐 입력 데이터 크기가 커지면 성능이 급격히 떨어지므로, 알고리즘 최적화 관점에서는 지양해야 합니다.