본문 바로가기

코딩 이야기/백준 풀이

백준 12764번: 싸지방에 간 준하 파이썬 코드(우선순위 큐)

반응형

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

import sys
import heapq

n = int(sys.stdin.readline())

heap = []
computers = [0 for _ in range(n)]
count = [0 for _ in range(n)]

su = 0

for _ in range(n):
    p,q = map(int, sys.stdin.readline().split())
    heapq.heappush(heap, [p,q])

while heap:
    temp = heapq.heappop(heap)
    for i in range(len(computers)):
        if computers[i] <= temp[0]:
            if computers[i] == 0:
                su += 1
            computers[i] = temp[1]
            count[i] += 1
            break

print(su)

for i in count:
    if i == 0:
        pass
    else:
        print(i, end= " ")
설명

computers와 count를 n 만큼 리스트로 만든다. 입력받은 값들을 시작 시간을 기준으로 우선순위 큐에 push해준다. 그리고 while문 안에서 계속 pop해주면서, computers를 0번 인덱스부터 n-1인덱스까지 for문을 돌리는데,(비어있을 때 가장 적은 번호부터 앉아야하기 때문.) 돌리면서 pop한 값보다 작고, 번호가 낮은 인덱스에 할당을 해주고 su += 1해준다. 그리고 해당 컴퓨터가 몇번 사용되었는지 알아야하기 때문에 count도 해당 인덱스에 += 1 해준다. 그리고 그 for문은 break 해준다.

 

문제점

골드 3 문제이긴하나, 문제 난이도는 골드 5~실버 1 정도라서 오히려 좀 쉽게 풀 수 있었다.

반응형