[python]18258_큐2

1 걸린 시간 : 30m

2 사용한 자료구조 및 개념 : 리스트, 큐

---

💡 문제풀이 아이디어 및 어려웠던 점

---

💫 아이디어

    1️⃣ 리스트를 활용하여 조건에 따라 결과 값 출력

---

👻 어려웠던 점

 

⏰ 시간초과 남 

❓이유

: 파이썬의 리스트의 가장 앞 데이터를 쓰거나 지우면 리스트 내부의 전체 데이터를 다시 써주어야함.

가장 앞의 데이터를 지울 경우,

해당 데이터를 지우고 전체 리스트의 데이터를 인덱스에 맞게 한칸씩 앞으로 당겨서 다시 씀.

따라서 q.pop(0)와 같이 가장 앞에 있는 리스트의 값을 pop시킬 경우,

전체 리스트를 다시 쓰기 때문에 시간 복잡도가 O(n)이 됨

 

❗해결

: 1️⃣ deque 사용
  2️⃣ 큐의 출구를 가르키는 인덱스 값을 가지고 있는 것

---

Solution Code & 주석

# 1️⃣ deque 사용
import sys
from collections import deque

tc = int(input())

q = deque([])
for t in range(tc):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        q.append(command[1])
    elif command[0] == 'pop':
        if len(q) == 0:
            print('-1')
        else:
            print(q.popleft())
    elif command[0] == 'size':
        print(len(q))
    elif command[0] == 'empty':
        if len(q) == 0:
            print('1')
        else:
            print('0')
    elif command[0] == 'front':
        if len(q) == 0:
            print('-1')
        else:
            print(q[0])
    elif command[0] == 'back':
        if len(q) == 0:
            print('-1')
        else:
            print(q[-1])

---

# 2️⃣ 출구 가리키는 값을 가지고 풀기
import sys

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

q = []
cnt = 0
for t in range(tc):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        q.append(command[1])
    elif command[0] == 'pop':
        if len(q) > cnt:
            print(q[cnt])
            cnt += 1
        else:
            print('-1')
    elif command[0] == 'size':
        print(len(q) - cnt)
    elif command[0] == 'empty':
        if len(q) == cnt:
            print('1')
            cnt = 0
            q = []
        else:
            print('0')
    elif command[0] == 'front':
        if len(q) > cnt:
            print(q[cnt])
        else:
            print('-1')
    elif command[0] == 'back':
        if len(q) > cnt:
            print(q[-1])
        else:
            print('-1')

---

GPT의 최적화

import sys
from collections import deque

def do_push(x):
    global size
    q.append(x)
    size += 1

def do_pop():
    global size
    if not size:
        return '-1'
    size -= 1
    return q.popleft()

def do_size():
    global size
    return str(size)

def do_empty():
    global size
    return '1' if not size else '0'

def do_front():
    if not size:
        return '-1'
    return q[0]

def do_back():
    if not size:
        return '-1'
    return q[-1]

command_dict = {
    'push': do_push,
    'pop': do_pop,
    'size': do_size,
    'empty': do_empty,
    'front': do_front,
    'back': do_back
}

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

q = deque([])
size = 0
for t in range(tc):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        command_dict[command[0]](command[1])
    else:
        sys.stdout.write(command_dict[command[0]]() + '\\n')