[PROGRAMMERS] 연습문제 : 야근지수 Python

오늘 풀어본 문제는 프로그래머스의 야근지수라는 문제이다.

문제를 간략히 요약하자면, 리스트안의 수들을 n만큼 줄일 수 있는데, n만큼 줄인 후 리스트의 제곱합이 최소가 된 경우의 값을 구하라는 문제이다.

문제를 읽었을때, 그리디하게 생각해서 가장 큰 수를 줄일수록 야근시간(리스트의 제곱합)이 줄어들지 않을까?라는 생각으로 풀었다.

works의 최대 길이가 20000이였기 때문에 이중 포문으로 가능할 수도 있겠다 싶어서 풀었고 다행히 통과하였다.

야근지수 문제풀이

가장 큰 값을 기준으로 잡고, works를 돌면서 기준과 같은 값은 -1 처리를 해주었다. 순회가 끝날 때마다, 기준값을 1씩 낮춰주었고, 기준값이 0보다 작아지거나, n이 0이 되면 답을 반환하였다.

사실 문제를 풀면서도 시간 초과가 될 줄 알았는데, 운이 좋게 통과됐다.

문제를 풀고나서 최근에 공부하고 있는 heap을 이용해서도 쉽게 답을 구할 수 있을 것 같아  heap라이브러리를 활용하여 다시 풀어보았다.

야근지수 문제풀이 2

heapq라이브러리는 최소힙만 구현해주기 때문에, 최대 힙을 구현하기 위해서는 -1을 곱해주어야 한다. 힙 자료구조는 자동으로 최솟값(이문제에서는 최댓값)을 기준으로 정렬을 해주기 때문에 heappop을 이용해서 항상 최댓값을 뽑아 줄 수 있다.

그렇기 때문에, 위에서의 문제풀이와는 달리 기준점을 잡을 필요없이 항상 max값을 뽑아서 1씩 줄인 후 리스트를 갱신할 수 있었다.

최근에 heap자료구조에 대해서 다시공부하지 않았더라면 두 번째 풀이를 생각하지 못한 채 넘어갔을 것이다. 무조건 라이브러리나 알고리즘을 많이 아는 게 답이 아닐 수도 있지만, 알수록 내 무기가 늘어가는 느낌이다. 

오늘도 하루한개 알고리즘 파이팅이다!

 

문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수