Lv2. H-Index (정렬) [X][O]

문제 출처: programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

 

1. 문제 이해

어떤 과학자가 발표한 논문 중 h번 이상 인용된 논문이 h편 이상일때 h의 최댓값 리턴

논문의 인용 횟수를 담은 배열 citations 길이는 1000이하
논문별 인용 횟수는 10000이하
 

2. 풀이 계획

1부터 인용횟수까지 for문 돌려서 (0부터하는건 어차피 의미 없음)
citations를 처음부터 끝까지 탐색하여 인용횟수 이상이면 cnt증가
마지막에 인용횟수와 cnt가 같으면 answer배열에 추가해줌
Answer 배열 정렬 후 마지막에 있는 원소 리턴
-> O(천만)

3. 구현

# 틀린 코드 (런타임 에러)

def solution(citations):
    MAX = max(citations)
    answer = []
    for i in range(MAX + 1):
        cnt = 0
        for c in citations :
            if i <= c :
                cnt += 1
        if i == cnt :
            answer.append(cnt)

    return answer[-1] # i가 작은것부터 큰 순서대로 넣어서 정렬해줄 필요 없었음

 

시간복잡도가 대략 천만이 나와서 아슬아슬하다고 생각했었는데 진짜 런타임에러가 나버렸다.

4. 검토 및 개선

def solution(citations):
    h = len(citations)
    citations.sort()
    
    for i in range(h) :
        if citations[i] >= h - i : # 논문이 인용된 횟수 >= 인용된 논문 개수 (i가 0부터라서 최댓값임)
            return h - i
        
    return 0 # 주의 : 모두 0인 경우

 

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

 
왜 정렬 ? 인용된 논문의 횟수 이상 인용된 논문의 개수를 쉽게 구하기 위해
왜 min ? 인용된 논문의 횟수와 인용된 논문의 개수가 모두 만족하는 값이 둘의 최솟값이기때문에
 

5. 배운점

1) map 함수

• map은 리스트의 요소를 지정된 함수로 처리해주는 함수
• map은 원본 리스트를 변경하지 않고 새 리스트를 생성
• list(map(함수, 리스트))
• tuple(map(함수, 튜플))

a = [1.2, 2.5, 3.7, 4.6]
a = list(map(int, a))

# a = [1, 2, 3, 4]

출처 : dojang.io/mod/page/view.php?id=2286

2) enumerate 함수

• 인덱스 번호와 컬렉션의 원소를 tuple형태로 반환

t = [1, 5, 7, 33, 39, 52]
for p in enumerate(t):
    print(p)
    
# 결과
(0, 1)
(1, 5)
(2, 7)
(3, 33)
(4, 39)
(5, 52)

출처 : wikidocs.net/16045


+) 20230316 다시 풀기

def solution(citations):
    answer = 0
    citations.sort()
    print(citations)
    
    # len(gt than num) >= num
    for num in range(min(len(citations), citations[-1]), -1, -1):
        cnt = 0
        for c in citations :
            if c >= num :
                cnt += 1
        #print(cnt)
        if cnt >= num :
            answer = num
            break
            
    return answer