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

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

문제

자연수 n과 자연수가 담긴 리스트 works가 입력으로 주어진다.
works의 길이가 $k$ 이고, works의 원소들을 $w_1$, $w_2$ .. $w_k$ 라고 하자,

works의 원소들의 값을 조금씩 감소시킬 수 있다.
얼마나? 감소시킨 양의 총합이 n이 될 때 까지.

이렇게 감소시킨 뒤에, ${w_1}^{2} + {w_2}^{2} + ... + {w_n}^{2}$ 의 최소값을 답으로 return하는 문제

접근

1

처음에는 반복문을 돌면서 전체 값을 평균으로 만들어주면 어떻게 되지 않을까..? 했지만
각 원소의 값을 감소시키는것만 가능하기 때문에 이 방법은 어려울것으로 보았다.

2

문제의 조건을 만족하기 위해서는 각 원소들의 차가 최소가 되어야 하는데,
각 원소들의 값을 증가시킬 수 없기 때문에
값이 상대적으로 큰 원소들의 값을 감소시켜주는 방식으로
전체 원소들간의 차가 적도록 만들어주어야 했다.
따라서 전체 원소들이 적어도 $m$ 이하의 값을 가지도록 만들어주기 위해
매개변수 탐색을 이용한 풀이로 접근했다.

코드

코드를 하나씩 살펴보자

solution()

solution()은 다음과 같은 형태이다.

def solution(n: int, works: list):
    answer = 0
    if n < sum(works):				# 1
        std = parametric_search(n, works)
        
        for i in range(len(works)):	# 2
            if works[i] > std and n - (works[i]-std) >= 0:
                n -= (works[i]-std)
                works[i] = std
                
        works.sort(reverse=True)	# 3
        for i in range(len(works)):
            if n > 0:
                n -= 1
                works[i] -= 1
            answer += works[i] ** 2
    return answer

주석 1번

works의 전체 원소의 합이 n보다 작은 경우,
모든 works 원소를 0으로 만들어줄 수 있기 때문에 항상 정답이 0이된다.
따라서 전체 원소의 합보다 n이 작은 경우에만 탐색을 통해 값을 도출하고,
그렇지 않다면 그냥 0을 return한다.

주석 2번

매개변수 탐색 로직이 구현되어있는 parametric_search() 함수의 반환값은
리스트 works가 원소로 가질 수 있는 최대값이 되어야 한다.

따라서, 이 반환값(std)보다 큰 값의 원소들을 모두 std로 만들어주고,
이때 감소값의 합이 가능한 총량인 n을 초과할 수 없기 때문에
for문 안쪽에 if works[i] > std and n - (works[i]-std) >= 0: 와 같이
조건문을 달아주었다.

주석 3번

가능한 최대값인 std보다 큰 모든 원소들을 std로 만들어 준 뒤에도
n은 아직 0이 아닐 수 있다.

이때, n이 works의 길이보다 큰 경우는 존재하지 않는데,
만약 그런 경우가 존재한다면 std의 정의에 위배되기 때문이다.

따라서, works를 내림차순으로 정렬해준 뒤 n이 0이 될 때 까지 값을 1씩 감소시켜준다.
n이 works의 길이보다 큰 경우가 존재하지 않기 때문에 항상 1씩 감소시켜줄 수 있다.

parametric_search()

def parametric_search(n, works):
    s = 0
    e = max(works)

    while s < e:
        m = (s+e)//2
        if is_possible(n, m, works):	# 1
            e = m
        else:
            s = m + 1
    return e

주석 1번

parametric_search()의 while문에서 m은 works의 원소의 가능한 최대값을 나타낸다.
is_possible()에 m을 전달하여, m이 최대값이 될 수 있는지를 판단하고

1) 가능하다면 탐색 범위를 값이 작은 쪽으로 감소시켜 m을 더 작은 값에서 찾고,

2) 불가능하다면 m이 너무 작은 값이라는 의미이므로
탐색 범위를 값이 큰 쪽으로 감소시켜 m을 더 큰 값에서 찾도록 구현했다.

is_possible()

def is_possible(n: int, std: int, works: list):
    m = n
    for i in range(len(works)):
        if works[i] > std:
            m -= works[i]-std
            if m < 0:
                return False
    return True

주어진 매개변수 std가 works의 최대값이 될 수 있는지 여부를 판단한다.
std가 너무 작다면,
모든 수를 std 이하로 만들기 전에 n이 0이 될 것이므로 False를 return하고
그렇지 않은 경우는 True를 return한다.

이 함수는 n의 값을 감소시키며 std가 최대값이 될 수 있는지 여부만을 판단해준다.
이 함수의 판단 결과를 이용해서 최대값을 줄여주는 일은
parametric_search()의 책임이다.