[정렬] 프로그래머스 H-Index

문제를 풀기 전 파이썬에서 리스트를 정렬하는 방식에 대해 간단하게 알아보자!
sort() 

• 리스트를 제자리에서(in-place) 수정하는 내장 함수
• 원본을 정렬하고, 수정한다.
• 리스트에게만 정의
• 그리고 리턴값이 None 이다.
• L.sort()
• reverse 매개 변수로 내림차순(True) 정렬 지정 가능

sorted() 

• 이터러블로부터 새로운 정렬된 리스트를 만드는 내장 함수
• 리스트에서만 정의되는 것이 아니라 모든 이터러블을 받아들임
• 리턴값이 정렬된 값이다.
• L2 = sorted(L1)
• reverse 매개 변수로 내림차순(True) 정렬 지정 가능

 
두 함수 모드 오름차순과 내림차순을 위해 불리언 값을 갖는 reverse 매개 변수를 받음

• reverse=True 로 지정시 내림차순 정렬

 
 

---

 

프로그래머스

 

 
어떤 과학자의 H-Index는 그 과학자가 발표한 논문 n편 중, h편 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면, h의 최대값을 뜻한다.

처음에는 무슨 뜻인지 정확히 이해가.. 어려워서 위키백과의 예시를 보니 확실해졌다.
 
예시) 송모양의 논문은 5개. 인용수는 각 9, 7, 6, 2, 1이다. 이때 h-index는?
3개 이상의 인용이 있는 3개의 출판물을 가지고 있기 때문에 3이다!
4개 이상의 인용이 있는 4개의 출판물은 없기 때문!
 
그렇담 이제 알고리즘을 생각해보자!
citations = [9 7 6 2 1]  내림차순으로 정렬 후!
citations[0] 개 이상의 인용이 있는 출판물의 개수 >= citations[0] 인가? -> 맞으면 그것이 h-index 이다.
이떄 "citations[0]개 이상의 인용이 있는 출판물의 개수"가 해당 인덱스 번호+1 이다.

(접은글은 나의 삽질이다)

삽질의 흔적

 

이렇게 생각한 후 코드를 작성했는데 처음에 너무 복잡하게 생각하여 그냥 이상하게 틀린 코드가 완성되었다... 대체 무슨 생각으로 쓴거니

def solution(citations):
    answer = 0
    cnt = 0
    
    citations.sort(reverse=True)
    size = len(citations)
    
    for x in range(1, size):
        cnt = 0
        while cnt < x:
            for i in range(size):
                if citations[i] >= x:
                    cnt += 1
        break
    answer = cnt 
    return answer

당연히 틀렸다.

정신 차리고 다시 문제를 보니...

 

"citations[0]개 이상의 인용이 있는 출판물의 개수"가 해당 인덱스 번호+1 이라는 것을 다시 생각!

def solution(citations):
    answer = 0
    
    citations.sort(reverse=True)
    size = len(citations)
    
    for i in range(size):
        if i+1 > citations[i]:
            answer = i
            break
    
    return answer

정답인줄 알았는데 채점 결과 틀렸다.

16 테스트 중에 1개가 틀림..
생각해보니 같은 인용수를 가진 논문이 있을 때 틀리는 것 같아서 코드를 수정했다.

def solution(citations):
    answer = 0
    
    citations.sort(reverse=True)
    size = len(citations)
    
    for i in range(size):
        if i+1 <= citations[i]:
                answer = i + 1 
    
    return answer

 

 
정답이당

---

참고 문헌

h-index 위키피디아 : https://en.wikipedia.org/wiki/H-index

h-index - Wikipedia

 
python sorting 공식문서 : https://docs.python.org/ko/3/howto/sorting.html

Sorting Techniques