[프로그래머스] 야근지수 - Python

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

아이디어

• works의 sum이 n보다 작으면 0 return
• works 배열을 heapq로 만들어 가장 큰 수가 앞으로 오게 만든다.
• n번 반복하여 works에서 가장 큰 수에 -1을 해준다.
• 각 자릿수의 야근지수를 구해 더하고 return

구현(실패)

import heapq

def solution(n, works):
    # 야근을 하기전에 일이 끝남
    if sum(works) < n:
        return 0
    
    #  -가 붙어있는 상태로 변환 최소힙
    works = heapsort(works)

    # 루트노드를 꺼내 1을 더해주고 다시 힙에 푸쉬
    for i in range(n):
        tmp = heapq.heappop(works)+1
        heapq.heappush(works, tmp)
    
    # 붙어있는 - 제거
    works = list(map(abs, works))

    # 야근 피로도 계산
    for i in range(len(works)):
        works[i] = works[i] ** works[i]

    return sum(works)

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, -value)
    return h

print(solution(4, [4, 3, 3]))

테스트 케이스는 다 맞아서 채점을 해봤는데 단 한 개의 테스트케이스만 통과...

런타임 에러와 시간 초과를 힌트로 다시 생각을 해보자

오류 해결 1

• 가장 먼저 1씩 빼서 0이 만들어졌을 때 0에 0을 제곱하여 1이 돼서 잘못된 답을 도출하는 경우 발견
• 예외처리를 해줘야겠다.

    # 야근 피로도 계산
    for i in range(len(works)):
        if works[i] == 0:
            continue
        else:
            works[i] = abs(works[i]) ** abs(works[i])

ㅋㅋㅋㅋㅋㅋㅋ..,,, 테케 하나 더 통과됐다..

다른 반례를 더 찾아봐야겠다.

오류 해결 2(하... 테스트 케이스 1개 실패)

• 힙으로 하지말고 sort를 통해 접근해 보자
• for문을 한 번만 돌면서 각 요소의 차이가 얼마나 나는지 확인하고 최댓값부터 몇씩 빼야 할지 구해보면 어떨까?
• 이후 야근 피로도를 계산하면 작업할게 훨씬 줄어들듯

def solution(n, works):
    # 야근을 하기전에 일이 끝남
    if sum(works) <= n:
        return 0
    works.sort(reverse=True)
    tmp = n
    idx = 0
    for i in range(len(works)-1):
        a = (works[i] - works[i+1])*(i+1)
        print(tmp, a)
        if tmp >= a:
            idx = i+1
            tmp -= a
        else:
            idx = i
            break
    
    #골고루 빼주기
    m = tmp // (idx+1)
    p2 = tmp % (idx+1)

    if tmp != n:
        for i in range(idx+1):
            works[i] = works[idx] - m
    for i in range(p2):
        works[works.index(max(works))] -= 1

    # 피로도 구하기
    for i in range(len(works)):
        if works[0] == 0:
            continue
        works[i] = works[i] ** 2
    print(works)
    return sum(works)

하 개빡친다 11번 너 뭔데 ㄴ미아ㅓ림;ㄴ아ㅓㄻ;ㅣ러

 

이거 질문에 올려놨으니 답변을 기다려봐야지...

진 다 빠졌다 쉬어야겠어