프로그래머스 - 야근 지수
: 계속 고민하던 포인트에서 막혀서 못푼 문제. 근데 그 해답이 heap에 있었던 문제이다. 계속 고민하던 포인트는 결국 계속해서 최대값에 -1을 해주면서 n을 소비(?)해 나아가는 것이 문제 풀이 방법인 것 까지는 알았는데, 계속해서 최대값을 찾느라 max()를 써서 O(N)이 되던지, 처음에 NlogN으로 정렬한 다음에 O(N)의 시간복잡도로 그보다 작은 수를 찾아서 넣고 다음 시행을 하던지의 방법밖에 떠오르질 않았다. 그러다보니 n이 최대 백만이라 시간초과를 해결할 수 없었음.
문제 해석
: 야근 지수는 퇴근후 남은 업무량들 각각을 제곱한 수들을 더해주면 나오는데, 이 문제에서는 그러한 야근지수를 최소로 만들고자 한다. 그럴려면 퇴근까지 남은 시간 n을 이용해서 남은 업무량을 최대로 줄여놔야한다. 이 때, n을 1투자하면 업무량 1을 감소시킬 수 있다는 조건이 있다. 즉, 1시간 일하면 업무량 1을 줄일 수 있는 것.
문제 풀이
: 일단 문제를 어떻게 풀어야할까를 고민해보면 나만의 표현으로 '최대값 죽이기'라는 표현을 생각했다. 결국 계속해서 업무량 중에 최대값을 다른 수들과 비슷하게 평준화해 나아가면서 최대값인 수를 줄이면서 수들을 낮은 수로 하향 평준화 해나가야 한다는 관점!.
풀이 설계
: 여기서 막혔는데, 최대값을 구하려면(계속해서) max를 계속해서 쓰거나 처음에 정렬을 해서 맨앞의 값에 -1을 하고 그 값보다 작은 값이 나올 때까지 탐색하다가 거기에 집어넣는 식으로 갱신해줘야한다. 두방법다 O(N)의 시간 복잡도가 걸린다(최대). 이 때, n이 최대 백만이므로..(잔인..)이렇게 하면 풀수가 없다. 내가 생각해낸 풀이는 아니지만(아쉽게도..) heap이라는 자료구조의 특성을 이용하면 풀 수 있다. 우선순위 큐라고도 불리는 힙은 이 문제처럼 '최소 혹은 최대값을 끊임없이 구하면서 값을 갱신해야할 때 쓰면 효율적인 자료구조'라고 할 수 있다. 힙에서 자료를 pop할 때 logN, 푸시할 때 lonN이기에 이 경우에는 n의 매시행마다 2logN이 걸린다. 그렇게 전체 시간복잡도가 NlogN으로 풀 수 있게 된 것.
구현 코드
1) 처음 설계 했던 코드
def solution(n, works):
answer = 0
# 그럼 여기서 좀더 효율적인 알고리즘을 찾아내야함
# index, max 를 안써도 되는 알고리즘
# 최초 한번만 nLOGn으로 sort하고,
# 그 다음부터는 최대값을 하나씩 -1 하면서
# 최대값이 변했나만 체크해주는식
works.sort(reverse=True)
while True:
if n <= 0:
break
if works[0] == 0:
break
works[0] -= 1
n-=1
# 여기서 가장 큰 값이 맨앞에 오게 하기만하면됨
# 이때 정렬 메서드를 안쓰고 최소의 시행으로 해야함
std = works[0]
for i in range(1,len(works)):
if std >= works[i]:
works[0],works[i-1] = works[i-1],works[0]
break
if i == len(works) - 1:
if std < works[i]:
works.pop(0)
works.append(std)
break
for el in works:
answer += el ** 2
return answer
2) 다시 짜본 코드
import heapq
def solution(n, works):
if n >= sum(works):
return 0
works = [-i for i in works]
heapq.heapify(works)
for i in range(n):
top = heapq.heappop(works)
# if top == 0 :
# break
new_top = top + 1
heapq.heappush(works, new_top)
return sum([i**2 for i in works])
: python에서 제공하는 heapq 모듈을 써서 풀었다. 이 때, heapq 모듈은 최소힙만 제공하기 때문에 처음에 모든 수를 음수로 바꿔줬다.
코멘트
: 이제 탐색공간을 바탕으로 완전탐색으로 풀 수 있는 단계까지는 확실히 금방 도달하는 것 같은데.. 그 다음에 내가 알고 있는(HEAP은 원래 알고 있었다..) 자료구조 및 알고리즘 지식으로 효율화 하는 단계에서 막힌다. 알고리즘, 자료구조 공부 따로 더 해야할듯.
