프로그래머스 - H Index (Java)

프로그래머스 H-Index 풀이 과정
1트 오답, 2트 정답(수정), 3트 정답(힌트). 조건문의 의미를 이해하는 데 시간이 걸렸다.
총 3번의 제출

---

H-Index란, n편의 논문 중 h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었을 때 가장 큰 h를 의미한다.

---

1트 (오답)

→ 최대 인용 횟수까지 cnt를 증가시키며 완전탐색
→ 각 cnt에서 cnt번 이상 인용된 논문 수(more)와 이하인 논문 수(less)를 셈
→ more >= cnt && less <= cnt이면 answer를 more로 갱신

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int max = citations[citations.length-1];

        int cnt = 0;
        int answer = 0;
        while(cnt<=max) {
            int more = 0;
            int less = 0;
            for(int i=0; i<citations.length; i++) {
                if(citations[i] >= cnt) more++;
                if(citations[i] <= cnt) less++;
            }

            if(more>=cnt && less<=cnt) answer = Math.max(answer, more);
            cnt++;
        }
        return answer;
    }
}

H-Index 정의를 코드로 옮기려 했는데, answer = more로 갱신하는 부분이 잘못됐다.
more는 "h번 이상 인용된 논문의 수"이지, h값 자체가 아니다.
예를 들어 citations = [3, 0, 6, 1, 5]일 때 cnt = 3이면 more = 3이지만, 이 둘이 같은 건 우연이지 항상 성립하지 않는다.
결국 h값이 뭔지 제대로 정의하지 못한 채 코드를 짰다.

---

1트 수정 (정답)

1트 코드에서 answer = Math.max(answer, more) 한 줄만 answer = cnt로 바꾸면 정답이 된다.

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int max = citations[citations.length-1];

        int cnt = 0;
        int answer = 0;
        while(cnt<=max) {
            int more = 0;
            int less = 0;
            for(int i=0; i<citations.length; i++) {
                if(citations[i] >= cnt) more++;
                if(citations[i] <= cnt) less++;
            }

            if(more>=cnt && less<=cnt) answer = cnt;
            cnt++;
        }
        return answer;
    }
}

answer = cnt가 맞는 이유

1트에서 answer = more로 쓴 게 왜 틀렸는지를 다시 보면 답이 나온다.

조건 more >= cnt && less <= cnt가 의미하는 건 "cnt번 이상 인용된 논문이 cnt편 이상 존재한다"는 것이다.
이 조건을 만족하는 cnt가 바로 h의 정의를 충족하는 h값이다.
우리가 찾는 건 h값, 즉 cnt이지 논문의 수인 more가 아니다.

while이 cnt를 0부터 max까지 순회하므로, 조건을 만족할 때마다 answer = cnt로 덮어쓰면 자연스럽게 가장 큰 h값이 answer에 남는다.

citations = [3, 0, 6, 1, 5] 기준으로 단계별로 보면:

cnt	more (cnt 이상 인용)	less (cnt 이하 인용)	조건 성립?	answer
0	5	1	✅	0
1	4	2	✅	1
2	4	2	✅	2
3	3	3	✅	3
4	2	4	❌	3
5	2	4	❌	3
6	1	5	❌	3

cnt = 3에서 마지막으로 조건이 성립하고, answer = 3이 된다.

1트에서 more를 담은 건, "more편 이상 인용됐으니 more가 h값 아닌가?"라는 착각 때문이었다.
하지만 h값은 "몇 번 이상 인용"에 해당하는 기준값이고, 그게 바로 cnt다.

---

2트 (힌트를 받아 정답)

→ 내림차순 정렬
→ 인덱스 i를 순회하면서 list.get(i) >= i+1이면 answer = i+1로 갱신

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        List<Integer> list = new ArrayList<>();
        for(int i : citations) list.add(i);
        Collections.sort(list, Collections.reverseOrder());

        int answer = 0;
        for(int i=0; i<list.size(); i++) {
            if(list.get(i) >= i+1) {
                answer = i+1;
            }
        }

        return answer;
    }
}

list.get(i) >= i+1 이 조건이 왜 맞는가

Q1. 내림차순 정렬을 왜 하는가

H-Index를 구하려면 결국 두 가지를 알아야 한다.

• 지금 기준이 되는 인용 수가 얼마인가
• 그 인용 수 이상인 논문이 몇 편인가

정렬 없이 이 둘을 알려면 1트처럼 매번 전체를 다 세야 한다.
그런데 내림차순으로 정렬하면 "몇 편인지"를 직접 셀 필요가 없어진다.

[3, 0, 6, 1, 5]를 내림차순 정렬하면 [6, 5, 3, 1, 0].
이제 왼쪽부터 논문을 하나씩 볼 때마다, 지금 보고 있는 논문까지는 전부 현재 값 이상 인용됐다는 게 자동으로 보장된다.
순서가 크기 순이니 당연한 얘기다.

Q2. i+1이 왜 논문 수인가

인덱스는 0부터 시작한다. 그래서 인덱스 i에 있다는 건 앞에 i개가 더 있다는 뜻이고, 지금까지 본 논문 수는 i+1편이다.

그리고 Q1에서 말한 대로, 내림차순이기 때문에 이 i+1편은 전부 list.get(i) 이상 인용됐다는 게 보장된다.

아래 표로 보면 직관적으로 이해가 된다.

[6, 5, 3, 1, 0] 기준:

i	list.get(i)	"이 값 이상 인용된 논문 수"는?
0	6	최소 1편 (인덱스 0만)
1	5	최소 2편 (인덱스 0~1)
2	3	최소 3편 (인덱스 0~2)
3	1	최소 4편 (인덱스 0~3)
4	0	최소 5편 (인덱스 0~4)

"이 값 이상 인용된 논문 수"가 항상 i+1이다. 별도로 세지 않아도 인덱스를 보면 바로 알 수 있다.

Q3. 그러면 조건 list.get(i) >= i+1은 무슨 뜻인가

H-Index 정의: h편 이상의 논문이 h번 이상 인용돼야 한다.

지금까지 정리한 걸 대입하면:

• i+1 = 지금까지 본 논문 수
• list.get(i) = 그 논문들의 최솟값 (= 이 값 이상 인용됐다는 기준)

list.get(i) >= i+1이면 → i+1편의 논문이 i+1번 이상 인용됐다 → H-Index 정의를 만족한다.

단계별로 보면:

i	list.get(i)	i+1	조건 성립?	해석	answer
0	6	1	✅	1편이 6번 이상 인용됨	1
1	5	2	✅	2편이 5번 이상 인용됨	2
2	3	3	✅	3편이 3번 이상 인용됨	3
3	1	4	❌	4편이 1번 이상 인용? → 조건 미달	3
4	0	5	❌	5편이 0번 이상 인용? → 조건 미달	3

i = 2에서 "3편이 3번 이상 인용됐다"가 성립하는 게 마지막이다. → answer = 3.

내림차순이라 i가 커질수록 list.get(i)는 작아지고 i+1은 커지기 때문에, 한 번 조건이 깨지면 그 뒤로는 다시 성립하지 않는다. 그래서 조건을 만족하는 마지막 i+1이 최댓값이고, 그게 answer에 남는다.

---

1트 / 1트 수정 / 2트 비교

	1트 (오답)	1트 수정 (정답)	2트 (정답)
접근 방식	완전탐색	완전탐색	정렬 후 한 번 순회
시간복잡도	O(n × max)	O(n × max)	O(n log n)
h값 결정	more로 잘못 설정	cnt로 정확히 표현	i+1로 정확히 표현
핵심 아이디어	h의 정의를 코드로 나열	h의 정의를 코드로 나열	정렬 후 인덱스가 논문 수를 대변

1트와 1트 수정의 차이는 딱 한 줄, more → cnt뿐이다.
로직의 방향은 처음부터 맞았는데, h값이 cnt라는 걸 놓쳤다.
2트는 완전탐색 없이 정렬만으로 같은 결과를 얻는다. 인덱스가 논문 수를 대신하기 때문에 별도의 카운팅이 필요 없다.

---

조건문 list.get(i) >= i+1 한 줄이 이해가 안 됐던 이유는, 내림차순 정렬 후 인덱스가 무엇을 의미하는지 파악을 못 했기 때문이다.
정렬 후 인덱스가 "지금까지 몇 편"인지를 나타낸다는 걸 이해하고 나면 조건이 자연스럽게 읽힌다.
앞으로 정렬 문제에서 인덱스가 카운터 역할을 할 수 있다는 걸 기억해두면 좋을 것 같다.