큐(Queue)

큐(Queue)

• 추상적 자료구조(ADT)라고 한다. 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의되어 있다.
• 프로그래밍 언어에 존재하지 않으므로 직접 구현해야 한다.
• FIFO(First In, First Out) : 먼저 들어온 게 먼저 나간다. 예) 선착순, 푸쉬 알림, 이메일 발송 등
• 배열이 수평으로 되어있다.
• 파이썬 리스트(List)를 활용한다.
• push는 .append()을 활용
• pop은 .pop()을 활용
• pop() : 맨 마지막 index 값을 출력해주고 제거시킨다.

활용 예시

프로그래머스 Level2 주식 가격

from collections import deque
def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        temp = queue.popleft()
        cnt = 0
        for q in queue:
            cnt += 1
            if temp > q:
                break
        answer.append(cnt)
    return answer

프로그래머스 Level2 프린터

def solution(priorities, location):
    answer = 0
    queue = [(i, p) for i, p in enumerate(priorities)]
    
    while True:
        temp = queue.pop(0)
        if any(temp[1] < q[1] for q in queue):
            queue.append(temp)
        else:
            answer += 1
            
            if temp[0] == location:
                return answer

프로그래머스 Level2 다리를 지나는 트럭

def solution(bridge_length, weight, truck_weights):
    time = 0 # 시간(answer)
    q = [0] * bridge_length # 다리를 건너는 트럭(Queue)
    while q:
        time += 1
        q.pop(0) # q에 자리가 비어야 truck_weights[0]이 들어올 수 있음
        
        # truck_weights에 대기 중인 트럭이 남아있을 경우 if문 진행
        # 대기 중인 트럭이 없을 경우 위의 time + 1 과 q.pop(0) 진행
        if truck_weights:
            if sum(q, truck_weights[0]) <= weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return time

프로그래머스 Level2 기능 개발

def solution(progresses, speeds):
    answer = []
    while len(progresses) > 0: # while progresses라고 해도 됨
        for i in range(len(progresses)):
            progresses[i] += speeds[i]
            
        cnt = 0
        while len(progresses) > 0 and progresses[0] >= 100:
            progresses.pop(0)
            speeds.pop(0)
            cnt += 1
        
        if cnt > 0:
            answer.append(cnt)
    return answer

모인 변수가 특정 조건마다 한 번에 쏟아져 나올 때

• 조건 : 1분마다 -10되고, 음수가 되면 나간다. 단, 내 앞이 나가야 나간다. (음수, 나가는 값)
• p = [25, 5, 20, 45, 15, 55]
• p = [15, -5, 10, 35, 5, 45] → 1분 경과
• p = [-5, -25, -10, 15, -15, 25] → 2분 경과 → -5, -25, -10 나감
• p = [35, -15, 25] → 15 + 20 = 35
• p = [-5, -55, -15] → 4분 경과
• p = []
• 1 + 2 + 4 = 7분 return

answer = 0
while p != []: # p가 전부 탈출하면 멈춘다.
	p0 = p[0]
	minute = (p0 // 10) + 1 # 15면 2분, 25면 3분

	for i in range(len(p))
		p[i] -= 10 * minute

	while p != [] and p[0] < 0: # p[0]이 음수가 아닐 때 까지 음수를 제거한다.
		p.pop(0)
	
	if p != []: # 전부 다 나간 게 아니면 맨 앞 + 20
		p[0] += 20

	answer += minute
return answer