Problem

---

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로래머스 정렬 분야의 level 2 문제다.
프로그래머스는 리트코드와 달리 적절한 import문을 추가해야만 제출된다.

Solution

---

고민

정렬을 해야 한다는 컨셉에는 도달했지만 문제풀이는 실패했다.

• 뒤에서부터 접근해야 한다는 생각을 하지 못했고, n-i 컨셉을 이해하지 못했다.
• h의 최댓값이라고 했으므로 Math.max()를 활용해야 한다는 생각도 해보았다.
• 투 포인터로 left 와 right의 범위를 계산해야 할까도 생각했다.
• brute force 풀이를 시도했으나 문제의 true 조건을 이해하지 못했다.

풀이

문제의 착각 포인트이면서 잘 알아야 하는 개념은 아래와 같다.

h번 이상 인용된 논문이 “h편 이상” 있어야 한다

인덱스 (i)	인용 횟수 (citations[i])	n − i (자신 포함 우측 논문 수)	조건: citations[i] ≥ (n − i)
4	6	1	6 ≥ 1 (참)
3	5	2	5 ≥ 2 (참)
2	3	3	3 ≥ 3 (참)
1	1	4	1 ≥ 4 (거짓)
0	0	5	0 ≥ 5 (거짓)

포인트

배열 안의 요소들 중에 정답이 있는게 아니다! 우연하게 배열 안 인용 횟수중 하나와 일치할 수 있겠지만 정말 우연이다.

핵심은 h번 이상 인용된 논문이 h편 이상 조건을 만족하는 최대 h값이라는 점이다.

Code

---

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;
        
        for(int i = n-1; i >= 0; i--) {
            if(citations[i] >= (n - i)) {
                h = n-i;
            }
        }
        
        return h;
    }
}

또 다른 풀이도 있다.
이것이 가능한 이유는 오름차순 정렬을 먼저 했기 때문이다. 정렬에 의해서 i에 대해서, i 이후에 원소들은 모두 i에 위치하는 원소보다 크다는 것이 만족된다.

citations[i+1] > citations[i]

이상 구간과 이하 구간이 이해가 어려워서 그림을 하나 더 그려보았다.

현재 논문 포함해서 남은 hIndex편의 논문이 각각 최소 hIndex회 이상 인용되었는가?”

(출처: https://gurumee92.tistory.com/177)

import java.util.*;

class Solution {
    public int solution(int[] citations) {
         // 1. citations 오름차순 정렬
        Arrays.sort(citations);
        
        int n = citations.length;
        int answer = 0;
        
        // 2. 0~n-1까지 반복
        for (int i = 0; i < n; i++) {
            int hIndex = n - i; // 현재 후보 h
            if (citations[i] >= hIndex) { // 조건 충족
                answer = hIndex;
                break; // 가장 큰 hIndex 찾으면 종료
            }
        }
        
        return answer;
    }
}