[Level 2] 정렬. H-Index

 문제 

https://programmers.co.kr/learn/courses/30/lessons/42747?language=python3 

코딩테스트 연습 - H-Index

 사용 언어 

Python3

 풀이 과정 

처음엔 정렬을 사용했지만 내 풀이대로 하면 굳이 정렬을 할 필요가 없어 뺐다. 그런데 딱 봐도 모든 경우의 수를 탐색해서 시간복잡도가 꽝이다. 알면서도 문제 그대로 구현하는 것 말고 내 머리로 풀 수가 없어 이렇게 풀었다. 그리고 제출 후 채점을 했더니..!

def solution(citations):
    criteria = len(citations)
    for i in range(criteria-1, -1, -1): # 마지막 인덱스값부터 -1까지 하나씩 줄어드는 루프
        h_index = i + 1
        count = 0
        no_count = 0
        for j in citations:
            if j >= h_index:
                count += 1
            if j <= h_index:
                no_count += 1
        if count >= h_index and no_count <= h_index:
            return h_index

통과 주루륵 뜨길래 그래도 답은 맞는구나 했는데 마지막 16번 케이스에서 실패?!

졸려서 바로 질문하기 들어가서 보니까 16번 테스트케이스는 [0, 0, 0, 0, 0]에 0이 나와야 하는 경우라고 한다.위 코드에 넣으면 None이 나왔고, 예외 처리를 해주지 않아서 예상되는 결과였다.어떻게 if문을 넣어볼까 하다가 생각해보니 for문 안에서 h-index를 구하지 못하면 0이 답이라고 생각해 맨 밑에 return 0만 추가해주었다.

9점 받았고 결과는 다음과 같다.

 제출 답안 

def solution(citations):
    criteria = len(citations)
    for i in range(criteria-1, -1, -1): # 마지막 인덱스값부터 -1까지 하나씩 줄어드는 루프
        h_index = i + 1
        count = 0
        no_count = 0
        for j in citations:
            if j >= h_index:
                count += 1
            if j <= h_index:
                no_count += 1
        if count >= h_index and no_count <= h_index:
            return h_index
    return 0 # for문 안에서 아무 값도 구하지 못할 때

 다른 사람 답안 

정렬 문제에 정렬을 사용하지도 않아 다른 사람의 풀이를 보고 배워야했다. 인기 많은(?) 코드가 두 가지 있었다.

1. 초깔끔한 코드

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

출처: 프로그래머스

오... 진짜 이해하기 어려웠던 코드

일단 enumerate 안에 start 매개변수는 인덱스의 시작값을 바꿀 수 있다. 그리고 위 코드를 보면

 

1) min(index,value) 부분은 가능할 수 있는 모든 h-index를 추출하는 부분
2) max(~) 값은 가능할 수 있는 모든 h-index 중 가장 큰 값을 추출하는 부분

 

으로 나뉘는데 예를들어 [6, 5, 4, 1, 0]의 경우에선 min~ 부분은 min(1, 6), min(2, 5), min(3, 4), min(4, 1), min(5, 0), 즉 해당 인용수 이상의 논문개수와 해당 논문의 인용수 중 더 작은 숫자를 고르는 작업을 하고(h-index로 가능한 숫자 추출), max~부분은 앞에서 골라진 (1, 2, 3, 1, 0) 중 가장 큰 숫자를 뽑아 실제 h-index를 구하는 방법인 것이다.

 

2. 가독성 좋으면서 역시 깔끔한 코드

def solution(citations):
    citations = sorted(citations)
    l = len(citations)
    for i in range(l):
        if citations[i] >= l-i:
            return l-i
    return 0

출처: 프로그래머스

가독성이 좋은거지 이해가 잘된다고는 말하지 않았다. 이것도 이해가 안돼서 댓글을 참고해야 했는데...

문제 설명은 [h번 이상 인용이 몇편인가? -> 그 편수가 h이상인가?] 의 순서로 사고하도록 적어두었지만

위의 경우는 [지금 몇 편이 남았는가? -> 모든 인용횟수가 이 값보다 큰가?(가장 작은 값이 이 값보다 큰가?)] 로 생각의 순서를 바꾼 것이라고 한다.