[Python]프로그래머스 - H-Index(level2)

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

코딩테스트 연습 - H-Index | 프로그래머스

틀린 풀이1

# 87.5점
def solution(citations):
    answer = 0

    while True:
        cnt = 0  # h편 이상인 논문 수
        for i in citations:
            if i >= answer:
                cnt += 1
        if cnt == answer:
            break;

        answer += 1

    return answer

단순하게 while문과 for문만 이용해서 풀었다.

테스트케이스 11, 16에서 시간초과

 

 

틀린 풀이2

# 81.3점
def solution(citations):
    answer = 0
    left, right = 0, len(citations) - 1

    while True:
        mid = (left + right) // 2
        cnt = 0
        for i in citations:
            if i >= mid:
                cnt += 1
        if cnt == mid:
            answer = mid
            break
        elif cnt > mid:
            left = mid + 1
        else:
            right = mid - 1

    return answer

틀린 풀이1에서 시간초과가 떠서 이번엔 이분탐색으로 풀었는데 이번엔 테스트케이스 9, 11, 16에서 시간초과...

 

 

성공한 풀이

def solution(citations):
    answer = 0
    left, right = 0, len(citations) - 1

    while True:
        mid = (left + right) // 2
        cnt = 0
        for i in citations:
            if i > mid:
                cnt += 1

        if cnt == len(citations):
            return cnt

        if cnt == mid:
            answer = mid
            break
        elif cnt > mid:
            left = mid + 1
        else:
            right = mid - 1

    return answer

틀린 풀이2에 중간에 if문 한개만 추가해줬더니 정답이란다.

다른 블로그 보고 [10, 50, 100]인 경우 h-index = 3이 되는 경우를 고려했다.

 

하지만 이 풀이도 완벽하지 않은게 테스트케이스1번에서 시간초과가 뜬다는 것 ([3, 0, 6, 1, 5]인 경우..) 아마 if i > mid에서 등호를 뺀게 문제가 되는 것 같다. 저기에 등호를 붙이면 다시 테스트케이스 11, 16이 실패뜸.

테스트케이스가 뭔지 몰라서 걍 포기했음ㅋㅋ

 

 

[2020.02.26 수정]

모두 성공한 풀이

def solution(citations):
    answer = 0
    left, right = 0, len(citations) - 1

    citations.sort()

    while True:
        mid = (left + right) // 2
        cnt = 0
        for i in citations:
            if i > mid:
                cnt += 1
		
        # 이걸 추가함
        if left > right:
            return cnt

        if cnt == len(citations):
            return cnt

        if cnt == mid:
            answer = mid
            break
        elif cnt > mid:
            left = mid + 1
        else:
            right = mid - 1

        print(left, right, mid, cnt)


    return answer


print(solution([3, 0, 6, 1, 5]))

테스트케이스1도 통과되게 수정함!!!

테스트케이스1의 경우 left = 3, right = 2, mid = 2, cnt = 3으로 무한루프를 돌아서 시간초과난거!!

그래서 left > right인 경우 걍 리턴하게 수정함