[프로그래머스] H-index 정렬문제 python (200713)

 

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

코딩테스트 연습 - H-Index

 

1. 문제 

---

문제 설명

 

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations                                                                                          return

[3, 0, 6, 1, 5]

3

입출력 예 설명

 

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

 

 

==> h회 이상 인용된 논문의 개수가 h 개 이상  

---

 

2. 풀이 

*** case 분석 

case1 - citation : [3,0,6,1,5]  ==>  3  

 

case2 - citation : [20,18,19,1] ==>  3

    * 1 이 아니라 3이다. 여기서 묻는건 h 의 최대값이기 때문에. 

      1번 이상인용된 논문의 수가 1 이상을 만족하긴 하지만, 제일 큰 수는 아님 

      4번 이상 인용된 논문의 수가 4 이상 만족(x)

      3번 이상 인용된 논문의 수가 3 이상 만족(o) 따라서 3 

 

총 세 가지 방법을 시도하였는데 문제에서 제공한 case1은 다 잘 작동되지만,

문제에서 제공하지 않고 따로 추가해본 case2는 딱 한 코드에서만 작동되었음.

 

 

2.1  풀이 1.  citation 값을 내림차순으로 하나씩 불러와서 해당 값보다 큰 값들의 개수세기 (오답임) 

def solution(citations):
    for thre in reversed(sorted(citations)):
        above_list = [i for i in citations if i >= thre]
        if (thre <= len(above_list)):
            return thre

case1 -> 3 (정답)

case2 -> 1 (오답) 

 우선 citation 값들을 불러오게 될 경우 문제점  -> 그 사이의 값 들을 고려하지 않게됨. *** 

20 [20]
19 [20, 19]
18 [20, 18, 19]
1 [20, 18, 19, 1]
중간 중간 값을 찍어 봤을 때 (좌측이 thre , 우측이 above_list ) 

18 과 1 사이의 값을 체크하지 않기 때문에 최대 h 값이 뽑히지 않음. 

 

 

2.2. 풀이 2. 최대 citation 값~0 까지 모든 값 탐색 

def solution2(citations):
    for thre in reversed(range(max(citations)+1)):
        above_list = [i for i in citations if i >= thre]
        if (thre <= len(above_list)):
            return thre

case1 -> 3 (정답)

case2 -> 3 (정답) 

 

20 [20]
19 [20, 19]
18 [20, 18, 19]
...
10 [20, 18, 19]
...
3 [20, 18, 19]

아까의 문제점을 해결했다.

하지만 이 경우 문제점은 citations 의 길이가 아주 많이 길고 값도 아주 클 때,

모든 숫자의 경우를 탐색해서 above_list 를 만드는 과정에서 메모리에러 발생가능성이 높음 

 

 

2.3. 풀이 3. 오름차순으로 정렬한 후,  인덱스를 활용해서 풀기  (BEST) 

 

""" 어떤 과학자가 발표한 논문n편 중, h번 이상 인용된 논문이 h편 이상이고  --> (( h 넘는 논문 갯수  >= h )) 

나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. """

def solution3(citations):
    citations = sorted(citations) # 오름차순으로 정렬
    for idx in range(len(citations)):
    
      	# (len(citations) - idx) : citations[idx] 번 이상 인용된 논문의 개수를 의미
        if citations[idx] >= len(citations) - idx: 
            return (len(citations) - idx)

1) 오름차순으로 정렬한다.  [1,18,19,20]

 

2) 한 인덱스 씩 살펴본다  

citations[0] == 1

len(citations) - idx  == 4-0 == 4 (전체 인용회수 중 1보다 크거나 같은 인용 회수의 개수)

     1<3

---------------------------------------

citations[1] == 18

len(citations) - idx  == 4-1 == 3 (전체 인용회수 중 18보다 크거나 같은 인용 회수의 개수)

     19>=3 이기 때문에, 3 출력 

---------------------------------------

 

 

3. 정리 

문제를 명확히 이해하기가 어려웠음. 

프로그래머스는 전체 케이스에서 막히는 경우가 많은데, 이걸 공개를 안해서 디버깅에 애먹음 (왜 틀렸는지 모르겠어서..)

주어진 예시 외에도 여러 경우를 다 고려하며 코드를 짜야할 듯