Programmers - 야근 지수

문제 링크

가장 높은 야근지수를 하나씩 줄이는게 가장 큰 이득을 얻을 수 있다.
하지만 n이 100만이고 작업의 길이가 최대 20000이니 하나씩 줄이면 시간초과가 발생한다.

따라서 다음과 같은 방법으로 문제를 해결하였다.

1. 가장 큰 값과 그다음 큰 값을 찾는다.
2. 주어진 n으로 가장 큰 값을 그다음 큰 값과 최대한 같게 맞춰준다.
   (모든 값이 같은 경우 그 다음 큰 값을 0으로 처리)
   • 가장 큰 값이 0인 경우 : 더 이상 process를 진행 할 필요가 없음 (return 0)
   • 주어진 n으로 가능한 경우 : 처리하고 남은 n을 return
   • 주어진 n으로 불가능한 경우
     모든 가장 큰 값들에 남은 n을 나누어 줄 수 있는 경우 : 나누어 주고 남은 n을 return
     모든 가장 큰 값들에 남은 n을 나누어 줄 수 없는 경우 : 차례로 나누어주고 return 0

process(): 작업을 진행하고 남은 n을 반환
solution(): n이 0이 될 때 까지 process()를 반복

# 작업을 진행하고 남은 n을 반환
def process(n, works):

    max = works[0]
    max_list = []
    second_max = 0

    if max == 0:
        return 0

    for (index, value) in enumerate(works):
        if value == max:
            max_list.append(index)
        else:
            second_max = value
            break

    required_n = (max-second_max)*len(max_list)
    if n >= required_n:
        for i in max_list:
            works[i] = second_max
        return n-required_n

    diff = n//len(max_list)

    # 다 나누는게 불가능한 경우 뺄 수 있는 만큼 1씩 제거
    # 남은게 없으니 return 0
    if diff == 0:
        for i in range(n):
            works[max_list[len(max_list)-1-i]] -= 1
        return 0

    for i in max_list:
        works[i] -= diff
    return n % len(max_list)


def solution(n, works):
    works.sort(reverse=True)

    while n > 0:
        n = process(n, works)

    # print(works)
    answer = 0
    for work in works:
        answer += work**2

    return answer