Programmers 42747. h-index

코딩테스트 연습 - H-Index

설계 방법 #

• citations 배열을 정렬한다.

• reduce 함수로 citations 배열을 순회하며

• h 를 최대값 n (citations.length) 부터 시작해서 현재 논문의 인용 회수가 h 번 이상이라면 h 를 반환하고,

  • 이 때 reduce 함수의 early break를 위해 arr 를 splice 한다.

• h 번 미만이라면 h 를 감소시킨다.

코드 #

function solution(citations) {
	return citations
		.sort((a, b) => a - b)
		.slice()
		.reduce((h, cur, _, arr) => {
			if (cur >= h) {
				arr.splice(1);
				return h;
			}
			return --h;
		}, citations.length);
}

function solution(citations) {
	return citations
		.sort((a, b) => a - b)
		.slice()
		.reduce((h, cur, _, arr) => {
			if (cur >= h) {
				arr.splice(1);
				return h;
			}
			return --h;
		}, citations.length);
}

시간 복잡도 #

• 정렬 : O(NlogN)

• 순회 : O(N)

→ O(NlogN)

어려웠던 점 #

• 처음에 문제 해결 방법이 쉽게 떠올랐고, 적중했지만, 방법이 떠오르지 않았다면 헤맸을 것 같다.

• 단항 증감 연산자에서 --x 또는 ++x 는 피연산자에 연산을 적용한 값을 반환하지만, x-- 또는 x++ 는 피연산자에 연산을 적용하기 전 값을 반환한다는 것도새로 알게 되었다. (그냥 먼저 적용한다, 나중에 적용한다 로만 이해했었음)

참고자료 #

How to early break reduce() method?