프로세스
1. 문제 이해
입력 / 출력 / 제약조건 분석
2. 알고리즘 설계
자료구조 + 시간복잡도 결정
3. 구현
실제 코드 작성
4. 최적화 / 리팩토링
더 좋은 방법 검토
내가 작성한 답안
package dailyalgo;
import java.util.*;
/**
* 1. 문제 이해
* - 과학자의 H-Index를 나타내는 값 h 구하기
* - n편 중 h번 이상 인용된 논문이 h편 이상
* - 나머지 논문이 n번 이하 인용될 경우 h의 최댓값이 과학자의 H-Index
*
* 2. 알고리즘 설계
* - 목표 시간복잡도: O(n)
* - 입출력 설명
* In: [3, 0, 6, 1, 5]
* Out: 3
* [해당 과학자가 발표한 논문은 5편
* , 그중 3편의 논문은 3회 이상 인용 -> (3, 6, 5)
* , 나머지 2편의 논문은 3회 이하 인용되었기 때문에
* , 이 과학자의 H-Index는 3
* (최소한의 인용횟수)
*
* - 제한 조건
* 1) 논문의 횟수는 1편 이상 1,000편 이하
* 2) 논문별 인용 횟수는 0회 이상 10,000회 이하
*
* 3. 해결방법
* - 빠른 비교를 위해 오름차순으로 정렬
* - 정렬 후 citations[i] >= (n - i)를 만족하는 최댓값 찾기
* - i번째 논문부터 끝까지 -> (n - i)개, n - i개의 논문이 citations[i] 이상 인용
*/
public class HindexEx {
public int solution(int[] citations) {
Arrays.sort(citations);
int n = citations.length;
for (int i = 0; i < n; i++) {
int h = n - i;
if (citations[i] >= h) {
return h;
}
}
return 0;
}
}
Java
복사
오늘의 진행내용 정리
[Day 7]
문제
- H-Index
- 논문의 인용 횟수 배열이 주어질 때
- h번 이상 인용된 논문이 h편 이상인 최대 h값을 구하는 문제
사용 알고리즘
- 정렬 (Sorting)
- Greedy + 조건 탐색
사용한 자료구조
- 배열 (Array)
시간복잡도
- O(N log N) -> 정렬
- O(N) -> 탐색
- 총: O(N log N)
배운 점
- H-Index는 "값"이 아니라 "개수 기준 문제"
(값 자체가 아니라 "몇 개가 조건을 만족하느냐"가 핵심
- 핵심 패턴, citations[i] >= (n - i)
- 정렬 후 역으로 보는 습관 중요
(큰 값부터 보면서 조건 확인)
C
복사