99클럽(3기) - 코테스터디 4일차 TIL # 정렬

프로그래머스 - H-Index

1. 문제 설명

어떤 과학자가 발표한 논문 n편이 인용된 횟수를 담은 배열(citations)이 주어진다. 논문 n편 중 h번 이상 인용된 논문이 h편 이상 인용되고, 나머지 논문이 h편 이하 인용되었다면 h의 최댓값을 H-Index라고 하며, H-Index를 구해서 반환해야 한다. 

 

2.  제한 사항

• 1 <= 과학자가 발표한 논문의 수 <= 1,000
• 0 <= 논문별 인용 횟수 <= 10,000

3. 입출력 예

 

 

---

 

4. 첫 번째 풀이 - Python

 'h번 이상 인용된 논문이 h편 이상 인용되었는지 판단하는 기준'을 설정하는 것이 핵심이었다. 이 말 자체를 이해하고 어떻게 문제 풀이에 적용할까 고민하는 시간이 제일 많이 소요된 것 같다. h의 최대값을 구해야하기 때문에 citations를 내림차순으로 정렬해서 가장 많이 인용된 논문부터 몇 편의 논문에 인용되었는지 판단해야한다고 생각했다. 이렇게 내림차순할 경우 각 요소는 인용 횟수를, 각 요소의 '인덱스 + 1'값은 현재까지의 논문의 개수를 나타낸다. 아래 표를 직접 써보면서 문제를 이해했다. 

 

for i in range(len(citations)): 로 순회를 하는 상황에서

citations는 내림차순 정렬을 했고, i는 0부터 시작하므로 항상 citations의 i번째 요소가 i + 1보다 크거나 같아야 한다. 하지만 i가 증가할 수록 어느 순간 논문 인용 횟수가 현재까지의 논문 개수보다 적어지는 지점이 온다. 그 때의 i값이 H-Index의 최대값이 된다. 

 

i	논문 인용 횟수(citations[i])	값 비교	현재까지의 논문 개수(i + 1)
0	6	>=	1번 이상 인용된 논문
1	5	>=	2번 이상 인용된 논문
2	3	>=	3번 이상 인용된 논문
3	1	<	4번 이상 인용된 논문
4	0	<	5번 이상 인용된 논문

 

 만약 모든 논문의 논문 인용 횟수가 현재까지의 논문 개수 이상이라면 과학자가 발표한 모든 논문이 논문 개수만큼 인용된 경우를 의미하기 때문에 논문의 개수인 len(citations)을 반환한다. 

def solution(citations):
    citations = sorted(citations, reverse=True)
    
    for i in range(len(citations)):
        if i + 1 > citations[i]:
            return i
            
    return len(citations)

 

 

5.  두 번째 풀이 - Java

 자바에서 원시타입 배열을 내림차순으로 정렬하려면 래퍼 클래스로 변환 후 Collections.reverseOrder()를 사용해야 한다. Collections.reverseOrder()는 래퍼 클래스로 구성된 '객체 배열'에만 적용이 가능하기 때문이다.  

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int[] citations) {
        // int 배열을 Integer 배열로 변환
        Integer[] citationsInteger = Arrays.stream(citations).boxed().toArray(Integer[]::new);
        
        // 내림차순 정렬
        Arrays.sort(citationsInteger, Collections.reverseOrder());;
        
        for (int i = 0; i < citationsInteger.length; i++) {
            if (i + 1 > citationsInteger[i]) {
                return i;
            }
        }
        
        return citations.length;
    }
}

 

 

6. 느낀점

구현하기 이전에 문제를 이해하고 어떻게 쉽게 풀어낼 것인지 구상하는 과정이 참 중요한 것 같다. 구현은 어렵지 않았지만 이 문제 자체를 이해하기가 어려웠다. 문해력을 키워야겠다,,