[백준] 18258 큐2 Python

1. 문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어진 명령을 처리하는 프로그램을 작성하시오 

 

https://www.acmicpc.net/problem/18258

2. 알고리즘 분류

* 자료 구조

* 큐

 

3. 접근 방식

큐 개념 정리 와 스택 개념 정리 도 했겠다, Stack 문제 풀이와 비슷하게 하면 되지 않을까? 

LIFO 인지 FIFO 인지만 구분하면 되니까! + 라고 생각했지만, 시간 초과가 떠서 검색해 보니

Queue 용도로 사용할 때는 deque 를 쓰는 게 좋다고 해서 deque 에 대해 공부했다 

deque 개념 정리 

4. 전체 코드

첫번째 시도 

10828 Stack 과 같은 개념으로 큐를 구현했다

# 정수를 저장하는 큐를 구현한 다음,
# 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오

# push x - 정수 x 를 큐에 넣는 연산
# pop - 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
#       만약 큐에 들어있는 정수가 없는 경우에는 -1 을 출력
# size - 큐에 들어있는 정수의 개수를 출력
# empty - 큐가 비어있으면 1, 아니면 0 출력
# front - 큐의 가장 앞에 있는 정수 출력, 없으면 -1 출력 
# back - 큐의 가장 뒤에 있는 정수 출력, 없으면 -1 출력

queue = []

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

def pop():
    if queue:
        firstpang = queue[0]
        del queue[0]
        print(firstpang)
    else:
        print(-1)

def size():
    print(len(queue))

def empty():
    print(0 if queue else 1)

def front():
    print(queue[0] if queue else -1)

def back():
    print(queue[-1] if queue else -1)

if __name__ == '__main__':
    n = int(input())

    for _ in range(n):
        c = input().split()

        if c[0] == 'push':
            push(int(c[1]))
        elif c[0] == 'pop':
            pop()
        elif c[0] == 'size':
            size()
        elif c[0] == 'empty':
            empty()
        elif c[0] == 'front':
            front()
        elif c[0] == 'back':
            back()

 

Stack 과 다르게 Queue 는 시간 초과가 떴다

 

두번째 시도

input() 은 시간이 오래 걸린다고 해서 sys.stdin.readline() 을 적용했다

https://www.acmicpc.net/problem/15552 

https://djm03178.tistory.com/21

문장 끝의 개행 문자 \n 를 없애주는 rstrip() 과 

공백을 기준으로 명령어를 분리하여 리스트로 저장해주는 split() 도 써 줬다

# 정수를 저장하는 큐를 구현한 다음,
# 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오

# push x - 정수 x 를 큐에 넣는 연산
# pop - 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
#       만약 큐에 들어있는 정수가 없는 경우에는 -1 을 출력
# size - 큐에 들어있는 정수의 개수를 출력
# empty - 큐가 비어있으면 1, 아니면 0 출력
# front - 큐의 가장 앞에 있는 정수 출력, 없으면 -1 출력 
# back - 큐의 가장 뒤에 있는 정수 출력, 없으면 -1 출력

import sys

queue = []


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

def pop():
    if queue:
        firstpang = queue[0]
        del queue[0]
        print(firstpang)
    else:
        print(-1)

def size():
    print(len(queue))

def empty():
    print(0 if queue else 1)

def front():
    print(queue[0] if queue else -1)

def back():
    print(queue[-1] if queue else -1)

if __name__ == '__main__':
    n = int(input())

    for _ in range(n):
        # c = input().split()
        # input() 은 시간 초과가 떠서, sys.stdin.readline() 사용 
        # rstrip() 문장 끝의 개행 문자를 없애기 
        # split() 공백을 기준으로 명령어를 분리하여 리스트로 처리 
        c = sys.stdin.readline().rstrip().split()

        if c[0] == 'push':
            push(int(c[1]))
        elif c[0] == 'pop':
            pop()
        elif c[0] == 'size':
            size()
        elif c[0] == 'empty':
            empty()
        elif c[0] == 'front':
            front()
        elif c[0] == 'back':
            back()

 

하지만 그래도 시간 초과가 떴다

 

세번째 시도

deque 의 popleft 로 pop 을 구현했다 

# 정수를 저장하는 큐를 구현한 다음,
# 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오

# push x - 정수 x 를 큐에 넣는 연산
# pop - 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
#       만약 큐에 들어있는 정수가 없는 경우에는 -1 을 출력
# size - 큐에 들어있는 정수의 개수를 출력
# empty - 큐가 비어있으면 1, 아니면 0 출력
# front - 큐의 가장 앞에 있는 정수 출력, 없으면 -1 출력 
# back - 큐의 가장 뒤에 있는 정수 출력, 없으면 -1 출력

from collections import deque
import sys

queue = deque()

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

def pop():
    if queue:
        # firstpang = queue[0]
        # del queue[0]
        # print(firstpang)
        print(queue[0])
        queue.popleft()
    else:
        print(-1)

def size():
    print(len(queue))

def empty():
    print(0 if queue else 1)

def front():
    print(queue[0] if queue else -1)

def back():
    print(queue[-1] if queue else -1)

if __name__ == '__main__':
    n = int(input())

    for _ in range(n):
        # c = input().split()
        # input() 은 시간 초과가 떠서, sys.stdin.readline() 사용 
        # rstrip() 문장 끝의 개행 문자를 없애기 
        # split() 공백을 기준으로 명령어를 분리하여 리스트로 처리 
        c = sys.stdin.readline().rstrip().split()

        if c[0] == 'push':
            push(int(c[1]))
        elif c[0] == 'pop':
            pop()
        elif c[0] == 'size':
            size()
        elif c[0] == 'empty':
            empty()
        elif c[0] == 'front':
            front()
        elif c[0] == 'back':
            back()