-
[우선순위 큐] 야근 지수 ***코딩 테스트/프로그래머스 2023. 4. 3. 20:17
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/12927
문제 풀이
- 큰 값을 모두 처리하는 것보다 큰 값들을 모두 균등하게 처리해야 제곱값들의 합이 최소가 나옴
- a^2 + b^2 <(a+b)^2 이기 때문(?)
- works에서의 최댓값을 항상 균등하게 맞춰가면서 -1 해야하므로 최댓값을 계속해서 뽑아줘야함
- 이를 정렬로 구현할 시 works는 최대 길이가 n*20,000*log(20,000) 이 발생. (works<=20,000 , n<=1,000,000)
- 대체안으로 항상 큰 값을 pop 해주는 최대 힙 우선순위 큐를 사용 (삽입,삭제 log(n))
소스 코드
import heapq def solution(n, works): if(sum(works)<=n): return 0 answer = 0 q = [] for i in range(len(works)): heapq.heappush(q,(-works[i])) #최대 힙을 사용할거라 음수값으로 넣어줌 while(n!=0): max_n = heapq.heappop(q)*(-1) max_n-=1 n-=1 heapq.heappush(q,(-max_n)) for i in range(len(q)): answer+=q[i]**2 return answer print(solution(4,[4,3,3]))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[해시] 베스트 앨범 (0) 2023.04.06 [연습 문제] 숫자 게임 (0) 2023.04.05 [그리디] 단속 카메라 (0) 2023.04.03 [동적 계획법] 등굣길 (0) 2023.03.31 [DFS/BFS] 단어 변환 (0) 2023.03.30