야근 지수

프로그래머스

 

야근 지수가 최소화되도록 일을 하는 방법을 구하면 된다.

야근 지수를 최소화시키려면 리스트 안 원소의 제곱의 합을 최소화시키면 되는데, 그러려면 제일 큰 수부터 작게 만들어야 한다는 생각이 들었다.

그래서 뭔가 최댓값을 뽑아줘야하므로 정렬 관련된 로직이 필요하다는 생각이 들었다.

최댓값을 뽑아 특정 값을 해당 최댓값에서 빼주고, 다시 또 최댓값을 뽑아서 특정 값을 해당 값에서 빼주고... 이 과정을 반복해야 하는데,

매번 정렬하게 된다면 시간복잡도가 증가하므로, 적절한 자료구조가 없을까 생각해보다가 문득! 머리에 우선순위큐가 스쳤다.

 

파이썬에서 우선순위 큐 자료구조를 이용할 때 주로 쓰는 모듈인 heapq는 최소 힙으로 구현되어 있기 때문에 큐에 원소를 넣거나 뺄 때 -를 붙여서 넣어주면 최대 힙처럼 사용할 수 있다.

 

우선순위 큐를 사용해 최댓값과 그 다음 큰 값을 뽑은 후, 최댓값을 그 다음 큰 값으로 바꿔주고 두 값을 다시 우선순위 큐에 넣는 과정을 반복한다.

만약 두 값이 같은 경우에는 최댓값에서 -1만 해준후 다시 우선순위 큐에 넣는다.

 

이 과정을 반복하다보면 리스트 안 원소의 제곱의 합을 최소화시킬 수 있다.

 

---

풀이 코드

import heapq

def solution(n, works):
    answer = 0

    # 만약 남은 일의 작업량이 N 이하인 경우에는 남은 작업량이 없으므로 피로도는 0
    if sum(works) <= n:
        return 0
    
    q = []
    # 파이썬의 최소힙으로 구성되어 있으므로 최댓값을 뽑기 위해 -를 붙여서 push하고 -를 붙여서 pop한다.
    for work in works:
        heapq.heappush(q, -work)
        
    while n > 0:
        first = -heapq.heappop(q) # 가장 많이 남은 일의 작업량
        second = -heapq.heappop(q) # 그 다음을 많이 남은 일의 작업량
        
        # first, second 두 수의 차이 to_do(해야 할 일의 양)
        to_do = first - second
        
        # 만약 가장 많이 남은 일의 작업량과 그 다음 많이 남은 일의 작업량이 같다면 둘 중 아무 일에서 1만큼 작업한다.
        if to_do == 0:
            first -= 1
            n -= 1
        # 작업량의 차이가 있다면
        else:
            # 만약 해야 할 일의 양이 n 이상인 경우에는 n만큼만 일을 할 수 있는 것이므로 first에서 n만큼 일을 하고 n = 0으로 바꿔 밑에서 새롭게 갱신된 first와 second를 우선순위 큐에 넣고 반복문을 종료할 수 있도록 만든다.
            if to_do >= n:
                first -= n
                n = 0
            # 해야 할 일의 양이 n보다 작다면 first에서 to_do만큼 일을 하고, n에서 to_do만큼 뺀다.
            else:
                first -= to_do
                n -= to_do
                
        # 새롭게 갱신된 first, second를 우선순위 큐에 다시 넣는다.
        heapq.heappush(q, -first)
        heapq.heappush(q, -second)
        
    # 야근 피로도 계산
    for work in q:
        answer += work*work
        
    return answer

 

프로그래머스 3단계 문제를 처음 풀어봤는데 잘 풀려서 뿌듯하다.

효율성 테스트도 한 번에 통과할 줄이야.

역시 알고리즘 문제는 최대한 많은 문제를 경험해야 잘 풀 수 있는 것 같다.

자신감을 가지자!