[Python] 백준 18258번 큐2 - deque안쓰고 풀기

큐 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
파이썬 : 3 초	512 MB	1730	610	482	37.923%

문제

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

명령은 총 여섯 가지이다.

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 복사

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1 복사

1
2
2
0
1
2
-1
0
1
-1
0
3

소스코드

deque 없이 구현한 queue

from sys import stdin
input()
s, com= [], stdin.readlines()
cnt = 0
for x in com:
    c = x.split()
    if c[0] == "push":
        s.append(c[1])
    elif c[0] == 'pop':
        if len(s) > cnt:
            print(s[cnt])
            cnt += 1
        else: print(-1)
    elif c[0] == 'size':
        print(len(s)-cnt)
    elif c[0] == 'empty':
        if len(s) == cnt :
            print(1)
            cnt = 0
            s = []
        else: print(0)
    elif c[0] == 'front':
        if len(s) > cnt: print(s[cnt])
        else: print(-1)
    elif c[0] == 'back':
        if len(s) > cnt: print(s[-1])
        else: print(-1)

• 결과

  • 메모리 : 281404KB
  • 시간 : 1908 ms

• 문제 풀이

  • 한 문장으로 요약하자면 "큐의 출구를 가르키는 index를 만든다."입니다.

  • 백준의 stack 문제를 먼저 푸셨다면 어떤 느낌인지 바로 감을 잡으셨을 것입니다. 전반적인 구현은 스택과 유사합니다. 해당 조건에 맞게 함수를 사용하면 됩니다. 하지만 스택과는 다르게 큐의 pop기능은 가장 앞에 있는 데이터를 출력해야합니다.

    • 2020/02/15 - [파이썬] - [Python] 백준 10828번 스택

  • 이때, 파이썬의 List를 이해하고 있어야합니다. 정확한 설명은 아니지만 대략 느낌을 알 수 있게 설명하겠습니다. 파이썬의 리스트의 가장 앞 데이터를 쓰거나 지우면 리스트 내부의 전체 데이터를 다시 써주어야합니다. 가장 앞의 데이터를 지울 경우를 생각해보겠습니다. 해당 데이터를 지우고 전체 리스트의 데이터를 인덱스에 맞게 한칸씩 앞으로 당겨서 다시 써주어야합니다. 따라서 stacklist.pop(0)와 같이 가장 앞에 있는 리스트의 값을 pop시킬 경우, *_전체 리스트를 다시 써주어야하므로 시간 복잡도가 O(n)이 됩니다. *_그러므로 시간 초과로 문제를 해결할 수 없습니다.

  • 따라서, 가장 앞을 가르키는 인덱스 값을 가지고 있는 것입니다. 위의 소스코드의 cnt가 해당 역할을 합니다. pop기능을 수행하면 가장 앞 인덱스 cnt에 해당되는 부분을 출력하고 cnt에 1을 더해서 가장 앞쪽을 가르키는 인덱스를 그 다음 칸을 가르키도록 합니다.

  • 초기화를 위해서 queue를 구현한 리스트가 비어있을 경우 전체 데이터를 초기화해주었습니다.

• 유사한 문제

  • 2020/02/15 - [파이썬] - [Python] 백준 10828번 스택

• 문제 출처

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