23.02.24 파이썬 코딩 퀴즈#171 야근 지수 (프로그래머스 스쿨)

이번 문제는 야근 지수 문제이다.

먼저 야근 지수란, 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값을 말한다.

한가지 조건은 퇴근까지 남은 시간은 N 시간이고, 1시간에 작업량 1 만큼을 처리할 수 있다는 점이다.

입출력 예 3번을 먼저보면, 현재 남은 작업량은 [1,1]이고 퇴근까지 3시간이 남아있다.

따라서 1시간에 1개의 업무를 처리 가능하기에, [0,0]이 되고 퇴근까지 1시간이 남아있게 된다. 따라서 피로도는 0이다.

 

입출력 예 1번을 보면 [4,3,3]이 있고 퇴근까지 4시간이 남아있다.

먼저 works[0]을 모두 해결했다고 가정하면 [3,3]의 작업량이 남았으므로, 3**2+3**2 = 18 의 피로도가 된다.

다음 [2,1,1]씩 해결하였다고 가정하면 [2,2,2]의 작업량이 남았으므로, 예시와 같이 12의 피로도가 된다.

 

즉 전달받은 n을 이용하여 works의 각 요소를 제거한 합이 n 이 되는 순간 각 요소들의 제곱합이 최소가 되는 값을 찾아야 하는 문제이다.

 

먼저 생각해야 할 문제는 피로도가 제곱들의 합이라는 점이다.

왜 굳이 제곱이라는 조건을 넣었을까?

예를들어 [4,3] 이라는 works 와 n = 1 일때를 생각해보자.

두 수의 제곱의 합은 16+9 = 25 이다.

만약 3을 1 감소시켜 [4,2]를 만든다면? 16 + 4 = 20 이다.

만약 4를 1 감소시켜 [3,3]을 만든다면? 9 + 9 = 18 이다.

즉 이 문제는 요소의 최대값을 찾아 그 값들을 1씩 감소시켜주는 작업을 n 번 반복하면 된다.

첫번째 작성한 코드이다. sort() 정렬을 이용하여 최대값을 배열의 제일 처음으로 이동 시키고 이 값들을 지속적으로 1씩 감소시켜나가면서 worked 변수값이 n이 될때까지 반복하는 코드이다.

그리고 최종적으로 만들어진 works를 반복문을 이용하여 제곱값들을 answer에 더해주었다.

역시 이번에도 효율성 테스트에서 걸린다...모든 테케를 1ms 미만으로 통과하였기에 기대해 보았지만, 역시는 역시다.

정렬에 걸리는 시간을 해결하기 위해 사용 가능한 라이브러리는 heapq 이다.

heapq 는 기본적으로 가장 작은 값을 index 0 으로 자동 정렬하며, 그 뒤로는 이분트리 구조로 값을 정렬해준다. 이를 최소힙 이라고 얘기한다.

그렇다면 최대힙은 어떻게 구현해야 할까?

정답은 heapq에 값을 튜플 또는 리스트 형태로 전달하여 사용하면 된다.

heapq는 기본적으로 전달받은 자료형 구조의 index 0 번째 값을 기준으로 정렬해 준다. 따라서 현재 값을 음수로 변환하여 그 값을 [-i, i] 형태로 넣어주면 가장 큰 i값이 가장 작은 -i 값이 된다.

이제 이를 while문을 통해 반복해주며 해당 heappop()을 이용해 0번째 요소를 가져오고 이 값의 index는 1을 증가시켜주고(음수이기 때문), 요소값은 -1 감소시켜준 다음 다시 heappush()를 통해 넣어주면 자동으로 정렬된 최대힙이 생성된다.

레벨3으로 넘어와서는 효율성 테스트가 좀 많이 타이트해졌다.

그리고 각 문제에서도 수학적인 사고를 많이 요구하기 시작했다.