[코테] 큐 queue

YB N·2025년 1월 20일

deq queue

코딩테스트

목록 보기

5/7

Tips

pop(0)과 popleft() 연산을 비교했을 때,
popleft()가 훨씬 1000배는 빠름!!
그렇기 때문에 queue를 사용할 때에는 list를 활용하기 보다는 deque를 queue로 활용할 것

DEQue = Double Ended Queue
양 끝에서 삽입과 삭제를 할 수 있는 큐를 구현한것이기 때문에 선입후출이 아닌 선입선출인 queue에서는 DEQue 자료구조를 사용하는 것이 좋음

DEQue를 활용하는 법
from collections import deque
queue = deque()

문제 15. 요세푸스 문제

내가 한 것:

## question 15
from collections import deque

def solution(N, K):
    peoples = deque(range(1, N+1))
    while len(peoples) != 1:
        for _ in range(K-1):
            peoples.append(peoples.popleft())
        peoples.popleft()
    return peoples[0]
print(solution(5, 2))

시간복잡도 O(N*K)
문제에서 N과 K는 1000이하 자연수 이므로
10^6이니까 10^8안쪽이라 괜찮음

문제 16. 기능 개발

내가 한 것:

## question 16
from math import ceil

def solution(progresses, speeds):
    release_day = 0
    release_funcs_num = 0
    release_funcs = []
    for i in range(len(progresses)):
        need_day = left_day(progresses[i], speeds[i])
        if need_day > release_day:
            release_funcs.append(release_funcs_num)
            release_day = need_day
            release_funcs_num = 1
        else:
            release_funcs_num += 1
    release_funcs.append(release_funcs_num)
    return release_funcs[1:]

def left_day(progress, speed):
    return ceil((100-progress)/speed)

# print(left_days(55, 5))

progresses = [93, 30, 55]
speeds = [1, 30, 5]
print(solution(progresses, speeds))

이 문제는 굳이 deque가 필요해 보이지 않는데..
popleft()를 사용하는 것도 아니고..

오 solution에서도 굳이 deque를 사용하지 않았군

보자보자 시간복잡도는 for문 하나 들어가니까 O(N)이군

문제 17. 카드 뭉치

내가 한 것:

## question 17

from collections import deque

def solution(cards1, cards2, goal):
    cards1 = deque(cards1)
    cards2 = deque(cards2)
    goal = deque(goal)
    card1 = cards1.popleft()
    card2 = cards2.popleft()
    while goal:
        target = goal.popleft()
        if target == card1:
            if len(cards1)>=1:
                card1 = cards1.popleft()
            else:
                card1 = None
            continue
        elif target == card2:
            if len(cards2)>=1:
                card2 = cards2.popleft()
            else:
                card2 = None
            continue
        else:
            return 'No'
    return 'Yes'


card1 = ['i', 'water', 'drink']
card2 = ['want', 'to']
goal = ['i', 'want', 'to', 'drink', 'water']

print(solution(card1, card2, goal))

내가 몰랐던 것:
처음에 cards1를 deque로 바꿀 때, 이 변환하기 위해서도 한번 list를 훑기 때문에 시간복잡도가 포함됩니다
그렇기 때문에, cards1과 card2의 사이즈를 N, goal의 사이즈를 M이라고 할 때,
시간복잡도는 O(N+M)입니다
또한, 나중에 while문으로 goal한번 싹 훑으니까 O(M)추가요~