더 맵게
https://programmers.co.kr/learn/courses/30/lessons/42626
내 풀이
정확성: 76.2
효율성: 23.8
합계: 100.0 / 100.0
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while scoville[0] < K:
if len(scoville) == 1:
return -1
answer += 1
a = heapq.heappop(scoville)
b = heapq.heappop(scoville)
heapq.heappush(scoville, a + b*2)
return answerscoville 을 heap 으로 바꿔줌 => min-heap 이용
가장 작은 값이 K 보다 커지면 모두 K 보다 큰 점을 이용
=> 스코빌 지수 최솟값이 K 보다 작을 동안
섞은 음식의 스코빌 지수
= 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)를 기반으로 최솟값 두개 pop 한 후 계산해서 push
스코빌이 하나만 남았을 경우는 섞을 수가 없으니까 return -1
디스크 컨트롤러
https://programmers.co.kr/learn/courses/30/lessons/42627
내 아이디어
매 초마다 요청할 수 있는 모든 디스크별 걸리는 시간을 계산해서 최솟값을 pick
시간 => 시점 + 소요시간 으로 계산
작업 중인 디스크만 소요시간 -1, 나머지는 +1
ex) [[0, 3], [1, 9], [2, 6]]
0초) 3 (0 + 3) -> 첫번째 디스크 pick
1초) 3 (1 + 2) or 10 (1 + 9)
2초) 3 (2 + 1) or 11 (2 + 9) or 8 (2 + 6)
3초) 12 (3 + 9) or 9 (3 + 6) -> 세번째 디스크 pick
but 구현은 못했다...
다른 사람의 풀이
정확성: 100.0
합계: 100.0 / 100.0
import heapq
def solution(jobs):
answer, now, i = 0, 0, 0
start = -1
heap = []
while i < len(jobs):
for j in jobs:
if start < j[0] <= now:
heapq.heappush(heap, [j[1], j[0]])
if len(heap) > 0:
current = heapq.heappop(heap)
start = now
now += current[0]
answer += (now - current[1])
i += 1
else:
now += 1
return int(answer // len(jobs))if start < j[0] <= now: => 요청할 수 있는 디스크들만 heap 에 push
걸리는 시간을 기준으로 정렬하기 위해 [j[1], j[0]] 로
start ~ now 범위만큼 디스크가 작업 중이라 생각
최솟값을 pop 해서 작업 처리
=> start, now update 하고 해당 디스크 소요시간 answer 에 더해주기
heap 이 비어있으면 요청시간이 오지 않았다는 것이므로 now + 1
마지막엔 평균 return
이중우선순위큐
https://programmers.co.kr/learn/courses/30/lessons/42628
내 풀이 1
정확성: 100.0
합계: 100.0 / 100.0
import heapq
def solution(operations):
heap = []
for op in operations:
op = op.split()
if op[0] == "I":
heap.append(int(op[1]))
elif op[0] == "D" and heap:
if op[1] == "1":
heap.remove(max(heap))
else:
heap.remove(min(heap))
if heap:
return [max(heap), min(heap)]
return [0, 0]그냥 리스트로 append 하고 max, min 값 pop
내 풀이 2
정확성: 83.3
합계: 83.3 / 100.0
import heapq
def solution(operations):
heap = []
for op in operations:
op = op.split()
if op[0] == "I":
heapq.heappush(heap, int(op[1]))
elif op[0] == "D" and heap:
if op[1] == "1":
heap.pop()
else:
heapq.heappop(heap)
if heap:
return [heap[-1], heap[0]]
return [0, 0]heap 이용
최댓값 return 할 때는 그냥 pop()
최솟값 return 할 때는 heappop()
근데.. 테스트케이스 하나가 통과되지 않음
이유 => heap[0] 는 최솟값이라는 보장이 있지만 heap[-1] 이 최댓값이라는 보장이 없음!!!
그럼 min-heap, max-heap 두가지를 써야할 듯
내 풀이 3
정확성: 100.0
합계: 100.0 / 100.0
import heapq
def solution(operations):
heap = []
max_heap = []
for op in operations:
op = op.split()
if op[0] == "I":
heapq.heappush(heap, int(op[1]))
heapq.heappush(max_heap, -int(op[1]))
elif op[0] == "D" and heap:
if op[1] == "1":
heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)
heapq.heappop(max_heap)
else:
heapq.heappop(heap)
max_heap = heapq.nlargest(len(max_heap), max_heap)[1:]
heapq.heapify(max_heap)
if heap:
return [-max_heap[0], heap[0]]
return [0, 0]Min-Heap 에서 최댓값 없애는 방법
heap = heapq.nlargest(len(heap), heap)[1:] heapq.heapify(heap)
nlargest(n, heap)=> 상위 n 개의 값만 가져옴
[1:]=> 최댓값 하나만 지우는 slicing
heapify=> 다시 heap 으로 만들어주기
를 참고해서 푼 풀이!!
min-heap, max-heap 두개 만들어서 똑같이 update 해준 후
마지막에 return 할 때 max_heap 은 마이너스를 붙여서 return
