[BOJ] 큐 문제 - 18258 큐 2, 2164 카드2 Python3

🔑 18258 큐 2

먼저, 큐와 스택의 차이점을 알아야 풀수있다.

스택: 후입 선출 / 큐: 선입 선출

스택은 top에서 삽입되고 top에서 삭제되지만,

큐는 한쪽(front)에선 삽입, 반대(read)쪽에선 삭제가 이루어짐

큐의 삽입연산: 인큐, 삭제연산: 디큐

이것만 알면 리스트 이용해서 구현은 금방한다.

문제는 시간초과 남.

시간초과 났던 코드

# 큐2

import sys
n = int(sys.stdin.readline().rstrip())
queue2 = []

def push(x):
    queue2.append(x)

def pop():
    if queue2:
        return queue2.pop(0)
    else:
        return -1

def size():
    return len(queue2)

def empty():
    if not queue2:
        return 1
    else:
        return 0

def front():
    if queue2:
        return queue2[0]
    else:
        return -1
def back():
    if queue2:
        return queue2[-1]
    else:
        return -1

for i in range(n):
    input_split = sys.stdin.readline().rstrip().split()
    order = input_split[0]
    
    if order == "push":
        push(input_split[1])
    elif order == "pop":
        print(pop())
    elif order == "size":
        print(size())
    elif order == "empty":
        print(empty())
    elif order == "front":
        print(front())
    elif order == "back":
        print(back())
    else:
        break

보니까 연산당 시간복잡도가 O(1)이어야 한다고 한다.

연산당 if else의 조건문만 쓰여서 O(1)이라 생각하였는데 뭐가문제임? 이라고 생각했는데

list로 선언해서 pop(0)를 하게 되면, 첫 번째 element를 pop 하고나서 나머지 element들의 인덱스를 1칸씩 당기는 과정에서 O(n)의 계산량이 발생한다. 따라서 deque를 이용한다.

라고 한다! 참 알아야 하는게 많아서 공부해따,,!

from collections import deque
queue2 = deque()

위와 같이 deque를 import 해주고, pop 부분만 deque 메소드로 바꾸어 주면된다.

내 정답 코드

# 큐2
from collections import deque
import sys
n = int(sys.stdin.readline().rstrip())
queue2 = deque()

def push(x):
    queue2.append(x)

def pop():
    if queue2:
        return queue2.popleft()
        
    else:
        return -1

def size():
    return len(queue2)

def empty():
    if not queue2:
        return 1
    else:
        return 0

def front():
    if queue2:
        return queue2[0]
    else:
        return -1
def back():
    if queue2:
        return queue2[-1]
    else:
        return -1

for i in range(n):
    input_split = sys.stdin.readline().rstrip().split()
    order = input_split[0]
    
    if order == "push":
        push(input_split[1])
    elif order == "pop":
        print(pop())
    elif order == "size":
        print(size())
    elif order == "empty":
        print(empty())
    elif order == "front":
        print(front())
    elif order == "back":
        print(back())
    else:
        break

🔑 2164 카드2

N = 4 인 경우,

카드는 위 < 1234 > 아래 , 1 버리고 < 234 >, 2 아래로 < 342 > 순서, 3 버리기 < 42 > 순서, 4 아래로 < 24 > 순서, 2 버리기

=> < 4 > 남음

front가 dequeue, front는 rear 위치로 이동, front dequeue, front는 rear 위치로 이동

즉 queue.popleft(), append(queue.popleft()) 의 반복이다!

앞에꺼 지우는 것은 deque모듈의 popleft를 이용하면 되고, 앞에꺼를 뒤로 보내는 것은 rotate(-1) 을 이용하여 왼쪽으로 1만큼 회전시켜주는 방법이 있다!

예를들어 1234에서 rotate( -1) 적용시키면 2341 이렇게 된다.

234에서 rotate(-1) 적용시에는 342

즉, rotate(-1) = queue.append(queue.popleft()) 이다.

코드

import sys

from collections import deque

n = int(sys.stdin.readline().rstrip())
card = deque()

for i in range(1, n+1):
    card.append(i)

while len(card)>1:
    card.popleft()
    card.append(card.popleft())
    
print(card[0])

rotate를 사용하면 조금 더 간단하게 나타낼 수 있다

card.append(card.popleft()) ⇒ card.rotate(-1) 이렇게만 해주면 됨!

근데 아직 아는걸로 풀었다. deque 관련해서 조금 더 공부가 필요할듯