프로그래머스 H-index (파이썬)

Level 2 정렬 

 

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

코딩테스트 연습 - H-Index

 

첫번째 제출 코드 

def solution(citations):
    answer = 0
    MAX = max(citations)
    n = len(citations)
    citations.sort()
    for h in range(0, MAX + 1):
        for i in range(n):
            if citations[i] < h:
                continue
            else:
                if h <= len(citations[i:]):
                    if len(citations[:i]) <= h:
                        answer = h
                        break
    return answer

[10,10,10,10,10] 의 경우 5가 나와야 하는데 10이 나왔습니다.

h를 0부터가 아니라 인용 수의 최소값 부터 반복문을 돌려서 1개의 경우만 틀렸었습니다.

 

결과는 위와 같이 성능이 매우 안좋았습니다. 

 

두번째 제출 코드

def solution(citations):
    answer = 0
    MAX = max(citations)
    n = len(citations)
    citations.sort()
    for h in range(0, MAX + 1):
        for i in range(n):
            if citations[i] < h:
                continue
            else:
                if h <= len(citations[i:]):
                    if len(citations[:i]) <= h:
                        answer = h
                        break
                else:
                    return answer
    #print(answer)
    return answer

if __name__ == "__main__":
    arr = [3, 0, 6, 1, 5]
    solution(arr)

 

첫번째는 h를 인용 수 중에서 무조건 가장 큰 값까지 반복을 했습니다.

하지만 h를 끝까지 반복 할 필요 없이 h > len(citations[i:]) 가 된다면 바로 return 시켜도 될 것 같아 코드를 바꿔 출력했습니다.

결과는 매우 좋았습니다. 

 

좋아요를 가장 많이 받은 코드

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

위 코드는 간결하고 신기해서 내부가 어떻게 작동하는지 파악하고 싶어 가져왔습니다.

먼저 역순으로 정렬을 하고 가장 (index, 인용 수) 를 인덱스 1부터 enumerate 로 묶습니다.

그 후 index와 인용 수 중 작은 값을 묶어 list로 만들고 그 안에서 가장 큰 값을 반환합니다

 

예를 들어 [3, 0, 6, 1, 5] 에서 

(1, 6) (2, 5), (3, 3), (4, 1), (5, 0)로 enumrate를 이용하여 묶고

각 원소 중 작은 값을 추출한 배열 (1, 2, 3, 1, 0)을 map으로 묶어 줍니다

마지막으로 max로 가장 큰 값인 3을 반환합니다.

 

핵심은 index와 인용수를 묶어 min으로 묶은 것입니다. 이게 가능한 이유는 현재 인용 수 이상인 개수가 인용 수의 배열에서의 index로 나타낼 수 있기 때문입니다.