프로그래머스 12927번 - 야근지수(★★★ / O / 1) : Python

개요

• 풀이 시간 : 30분
• 시간 제한 : -
• 메모리 제한 : -
• 기출 : 프로그래머스 연습문제
• 링크 : https://programmers.co.kr/learn/courses/30/lessons/12927

문제

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

입력 형식

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

해결방법

문제 이해하기

이 문제는 원리는 간단한 편이다. 가장 남은 일의 작업량이 큰 놈을 최우선적으로 줄어줘야 제곱을 했을때 야근 피로도를 최소로 구할 수 있다. 예를 들어 [6, 5, 2]에다가 n은 4라고 했을때 [4, 3, 2]가 되는 것처럼 말이다.

알고리즘 - 메모리제이션

하지만 잘 생각해보면 어떻게 이를 균등화(?) 시킬 수 있을까 싶다. 매번 최대값을 구해서 하나씩 빼주기에는 너무 비효율적이다. 여기서 약간 고민을 했다. 그러다가 메모리제이션 방식을 사용하면 어떨까 싶었다.

1. works의 원소 최대값은 50000이므로 해당 크기만큼 배열(메모리제이션)을 만든다.
2. works 원소 값을 인덱스로 삼고 해당 인덱스에 대한 값은 1씩 증가시켜준다.
3. 해당 배열에서 가장 큰 원소부터 찾아서 하나씩 감소시켜주면 된다. 이를 n이 0이 될때까지 반복해준다.
4. 그렇게 구한 배열에서 야근 지수를 계산해주면 끝

✍️ 혹은 힙을 이용해서 나와 비슷하게 구할 수도 있다. 은근 힙을 사용하는 사람이 많았다.

Python

내 코드

def solution(n, works):
    sumWorks = sum(works)
    
    if sumWorks <= n:
        return 0
    else:
        arr = [0] * 50001
        for work in works:
            arr[work] += 1
        
        for i in range(50000, 0, -1):
            while arr[i] != 0 and n != 0:
                arr[i] -= 1
                arr[i - 1] += 1
                n -= 1
            if n == 0:
                break
        
        result = 0
        for i in range(50000, 0, -1):
            if arr[i] != 0:
                result += (i ** 2) * arr[i]
        return result
        
                

✍️ 오. 메모리제이션을 활용해서 잘 풀었구만. 꼼수가 늘었어~

다른 코드 - 힙

import heapq

def solution(n, works):
    answer = 0
    heap = []
    if sum(works) <= n:
        return 0
    
    for w in works:
        heapq.heappush(heap, -w)

    while n != 0:
        w = heapq.heappop(heap)
        w += 1
        n -= 1
        heapq.heappush(heap, w)

    for h in heap:
        answer += h ** 2
    
    return answer

✍️ 힙을 사용했다는 점 빼고는 나와 코드가 매우 유사한듯하다.

다른 코드 2 - 정렬

def solution(n: int, works: list):
    pointer = len(works) - 1
    works.sort()

    while n > 0:
        n -= 1
        if works[pointer] > 0:
            works[pointer] -= 1
        
        if pointer == 0:
            pointer = len(works) - 1
        else:
            if works[pointer] < works[pointer - 1]:
                pointer -= 1
            else:
                pointer = len(works) - 1

    return sum(map(lambda x: x ** 2, works))

✍️ 오... 이 방법 참신했다. 정렬을 한 다음에 pointer를 해서 큰 놈을 우선적으로 하나씩 빼준다음, pointer를 옮겨야할지 말아야할지 결정하는구나... 굿