99클럽 코테 스터디 8일차 TIL + 정렬(H-Index)

오늘의 과제

프로그래머스 Lv.2에 정렬로 분류된 H-Index입니다.

 

어제에 이어 정렬 문제입니다.

문제

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

프로그래머스

 

 

입력 제한도 여유 있어 별 생각없이 Arrays의 sort API를 이용해 쉽게 풀어낸 문제입니다.

 

문제를 보면 h번 이상 인용된 논문이 h편 이상이고 나머지는 h번 이하 중 h의 최댓값을 찾으라고 합니다.

 

이상과 이하의 기준점인 h를 찾아야 하니

인용 수가 총 논문 수 -  idx보다 크거나 같을 때 까지순회하며 찾으면 됩니다.

 

예제 입력을 살펴보면

{3, 0, 6, 1, 5} 가 주어집니다.

 

이를 Arrays.sort를 통해 정렬하면 {0, 1, 3, 5, 6} 이 되고

위 계산식에 따르면 3 >= 5 - 2가 되니 3을 리턴하게 됩니다.

 

이해가 안되면 Array.sort를 하지 않고 풀어보면 조금 쉽게 이해가 될 수 있습니다.

 

{3, 0, 6, 1, 5}를 보겠습니다.

 

h에 각 요소를 순차적으로 대입해보겠습니다.

 

3번 이상 인용된 논문이 3편 이상이고, 나머지 인용 수는 3번 이하여야 한다. == true , Max = 3

0번 이상 인용된 논문이 0편 이상이고, 나머지 인용 수는 0번 이하여야 한다. == false, Max = 3

6번 이상 인용된 논문이 6편 이상이고, 나머지 인용 수는 6번 이하여야 한다. == false, Max = 3

1번 이상 인용된 논문이 1편 이상이고, 나머지 인용 수는 1번 이하여야 한다. == true, Max = 3

5번 이상 인용된 논문이 5편 이상이고, 나머지 인용 수는 5번 이하 여야 한다. == false, Max = 3

 

보이시나요?

정렬 없이  h번 이상 인용된 논문을 기준으로 위 아래로 찾으려면 n² 반복해야 합니다.

(3번 기준 찾을 시 0, 6, 1, 5와 비교해봐야 합니다.)

 

하지만 정렬 후 찾는다면 해당 값의 idx보다 크다면 더 많이 인용된 논문일 것이고,

작다면 더 적게 인용된 논문일 것입니다.

 

따라서 citations.length - i는 기준값 대비 더 많이 인용된 논문의 수 가 됩니다.

 

코드입니다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        // 배열 정렬
        Arrays.sort(citations);
        
        for (int i = 0; i < citations.length; i++) {
        // 
            if (citations[i] >= citations.length - i) {
                answer = citations.length - i;
                break;
            }
        }
        return answer;
    }
}

 

배운 점

사실 이전에 풀었던 문제라 초기화 후 다시 풀어도 쉽게 풀었던 문제입니다.

 

풀이한지 좀 오래 되었어도 기억속 어딘가에는 남아 조금만 건드려주면 금방 나와서 저를 도우는 것 같네요.

 

 

 

오늘의 한줄평

집중적으로 힘들게 공부했던 기억은 잊혀져도 몸이 기억한다.