📖 문제

📝 풀이과정

1. 먼저 어떤 과학자가 발표한 논문의 인용 횟수를 담은 리스트 citations를 오름차순으로 정렬한다. -> h번 이상 인용된 논문의 개수를 세기 편해진다.
2. h를 주어진 citations에서 가장 인용이 많이 된 논문의 인용 횟수의 절반을 초깃값으로 설정한다. -> 연산의 횟수를 줄일 것을 기대했다.
3. citations에서 h와 같거나 큰 값을 갖는 것의 위치를 찾는다. -> idx
   만약 h와 같거나 큰 값을 갖는 것이 없다면 while문을 탈출
4. h번 이상 인용된 논문들의 개수가 h이상이라면 일단 h를 정답을 담는 변수 answer에 담고 h를 1만큼 증가시켜본다.
   아니라면, answer가 0이 아닌 경우에만(while문이 무한 루프를 도는 것을 방지) h를 1만큼 감소시킨다.

⌨ 코드

def solution(citations):
    answer = 0
    # 1. citations 오름차순으로 정렬 
    citations.sort()

    # 2. h 초깃값 설정
    h = max(citations) // 2
    while 0 <= h :
        idx = -1 # h와 같거나 큰 것이 없는 것을 대비하기 위해서
        # 3. citations에서 h와 같거나 큰 값의 위치 찾기
        for i in citations:
            if h <= i:
                idx = citations.index(i)
                break
        # 없다면 while문 탈출
        if idx == -1:
            break
        # 4. h번 이상 인용된 논문들의 개수가 h이상이라면
        if h <= len(citations) - idx:
            answer = h
            h += 1
        # 4. h번 이상 인용된 논문들의 개수가 h미만이라면
        else:
            if answer != 0:
                break
            h -= 1
    return answer

☺ 느낀점

문제를 풀면서 이분탐색과 비슷하다는 느낌을 받았다. 이분탐색도 어차피 리스트가 정렬되어있는 상태에서만 풀 수 있어서 그런 것 같다.
그런데 다른 사람들의 풀이를 보니까 굳이 이분탐색처럼 문제를 풀지 않아도 됐었다.
다음 코드를 보자.

def solution(citations):
    citations = sorted(citations)
    
    # l은 어떤 과학자가 쓴 논문의 총 개수
    l = len(citations)
    for i in range(l):
        # 현재 위치한 인덱스(i) 이후로 (l-i)편이 남아있다.
        # 그러면 남은 (l-i)편의 논문이 모두 (l-i)번 이상 인용된 논문이면 정답
        if citations[i] >= l-i:
            return l-i
    return 0

어떻게 이런 생각을 했을까!!! 정말 감탄스럽다
위 코드의 주석에서 l-i를 h라고 바꾸기만 한다면 문제에서 제시한 조건과 일치함을 손쉽게 알 수 있다.
단, 문제에서는 'h번 이상 인용된 논문이 h편 이상 남아있는가?'라고 제시했지만 위 코드는 'h편 남은 논문들이 h번 이상 인용됐는가?'라는 방식으로 푼 차이만 있다.
같은 문제를 보더라도 해석을 좀만 달리하면 더 쉽게 풀 수 있다는 게 너무 신기했다....
나도 꾸준히 하다보면 저런 통찰력을 가지게 되는 날이 오겠지..?