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

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

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. 효율성을 위하여 최대힙을 사용한다.

2. works의 합이 n보다 작은 경우에는 모든 작업을 해결할 수 있는 경우이기 때문에 바로 0을 리턴한다.

3. 힙에 works 값들을 담아준다.

4. 가장 큰 값을 하나씩 빼줘야 제곱을 했을 때, 최솟값이 되기 때문에 힙에서 가져온 값을 -1 해주고 다시 힙에 넣어준다.

5. 힙의 모든 원소를 제곱하여 더해준다.

import heapq #1번

def solution(n, works):
    answer = 0
    heap=[]
    if sum(works)<n: #2번
        return 0
    
    for i in works: #3번
        heapq.heappush(heap, -i) #힙은 최소힙이 기본이기 때문에 -를 사용하여 최대힙으로 만들어준다.
    
    for i in range(n): #4번
        value=-heapq.heappop(heap) 
        heapq.heappush(heap,-(value-1))
        
    for i in heap: #5번
        answer+=(-i)**2
    return answer

모든 원소를 제곱하고 더했을 때, 최솟값이 나와야하기 때문에 가장 큰 값에 -1을 해주는 것이 관건이었다.

처음에는 max()를 사용하여 일일이 가장 큰 값을 찾아서 빼주는 코드를 작성하였다.

max()를 사용한 탓에 정확성은 있었으나 효율성이 엉망이었다.

따라서 최소, 최대 관련 문제는 힙을 우선적으로 사용하는 것이 좋을 듯하다.

 

처음 작성한 코드

def solution(n, works):
    answer = 0
    if sum(works)<n:
        return 0
    for i in range(n):
        works[works.index(max(works))]-=1
    for i in works:
        answer+=i**2
    return answer