우선순위큐

[python] 백준 - 12764. 싸지방에 간 준하

🤔문제 해결 우선순위 큐 대기중인 사람과 먼저 사용중인 사람 중 가장 빨리 끝나는 곳과 비교 대기중인 사람보다 늦게 끝나면 새로운 자리로 배정 기존의 사람이 끝나는 곳이 있으면 그게 여러 곳이 있으면 끝나는 곳을 다 뽑아서 남는 자리 우선순위 큐에 넣는다. 더 이상 없을 때 남는 자리 우선순위 큐에서 자리르 하나 뽑아서 배정한다. 사용중인 컴퓨터 끝나는 시간과 자리번호가 담긴 우선순위 큐 남아있는 자리가 담긴 우선순위 큐 이렇게 해서 두개를 사용했다. 우선순위 큐를 두개 써야해서 헷갈렸던 문제 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) logs = [list(map(int, input().split())) for ..

[python] 백준 - 19598. 최소 회의실 개수

🤔문제 해결 우선순위큐 회의를 오름차순으로 정렬한다. 사용한 회의실의 끝나는 시각을 배열로 만든다. 우선순위큐로 사용할 것 회의를 하나씩 꺼내서 가장 빨리 끝나는 회의실과 회의 시작 시간을 비교 회의 시작 시간이 더 빠르면 회의실 추가 회의 시작 시간이 더 늦으면 해당 회의실의 끝나는 시각 업데이트 🍞 heapreplace는 가장 작은 요소를 빼고, 추가할 요소를 집어 넣는다. ( pop 후 push 를 합친것 - 더 빠르다고 한다.) 💻소스 코드 import sys import heapq input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(..

[python] 프로그래머스 - 무지의 먹방 라이브(2019 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv4 | 우선순위 큐? 가장 처음 생각난건 역시 1초씩 전부 돌아보자!! 하지만 역시나 시간초과 발생 😂🤣 음식을 한꺼번에 뺄순 없을까 생각해서 가장 적은 음식의 수만큼 사이클을 돌기로 했다. 예를 들어 음식이 [ 5,5,3,3,6 ] 이라면 3만큼 한꺼번에 돌아주는 것이다. 음식이 3만큼 있고, 전체 길이가 5 이므로, 15초 뒤에는 [ 2,2,0,0,3 ] 이 된다고 상상만!!! 직접 빼주고 하면 시간 초과 다음은 2만큼 있고, 전체 길이가 3 이므로 (0은 취급 안함), 6 초 뒤에는 [ 0,0,0,0,1 ] 역시 상상만 하자 위의 방법 처럼 한꺼번에 빼주는데 가장 적은 음식은 어떻게 꺼내냐하면 바로 힙큐를 쓰자. 힙큐에 음식의 양과 해당 음식의 번호를 차례로 넣으면 가장 작은 음식을..

[python] 프로그래머스 - 디스크 컨트롤러

🤔문제 해결 Lv3 | 우선순위 큐 파이썬에서는 heapq 를 사용합니다. 먼저 현재 시간을 항상 계산해 줍니다. 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다. 힙큐에 값이 여러개 들어있더라도, heappop() 을 하게 되면 작업시간이 가장 짧은 작업이 나오게 됩니다. ( 힙큐에서는 최솟값이 나오게 됩니다 ) 작업시간만큼 현재시간 을 늘려주고, 해당 작업의 대기시간+작업시간 을 따로 저장해 둡니다. 한 작업이 끝나고 나면 시간이 흘렀기 때문에 다시 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다.(아까 넣은 작업 제외) 똑같이 heappop() 으로 현재시간과 작업시간을 저장합니다. 💨 업무투입시간이 오름차순 정렬이 안되어있어서 먼저 정렬을 해줘야 합니다. 💻소스 코드 import..

[python] heapq(힙큐, 우선순위큐)

📗heapq란? 간단하게 리스트내에서 가장 작은 값이 맨처음위치(인덱스 0)애 오게 해주는 내장 모듈 우선순위 큐라고 알면 쉽다. 🔵 시작하기 import heapq 🔵 선언하기 보통 리스트를 선언하는 것처럼 만든다. heap_list = [] 🔵 원소 추가하기 ( heapq.heappush(리스트, 값 )) - 아래 보이는 것 처럼 가장 작은 값이 맨 처음 위치에 왔다. 시간복잡도 O(logn) heapq.heappush(heap_list, 5) heapq.heappush(heap_list, 10) heapq.heappush(heap_list, 99) heapq.heappush(heap_list, 2) print(heap_list) # [2, 5, 99, 10] 🔵 원소 삭제하기 ( heapq.heap..