둔필승총

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

from collections import deque
import sys
input = sys.stdin.readline
q=deque()
n= int(input())
for i in range(n):
    question = input().split()
    if len(question)==2:
        order = question[0]
        number = int(question[1])
        q.append(number)
    else:
        if question[0]=='pop':
            if len(q)==0:
                print(-1)
            else:
                print(q.popleft())
        elif question[0]=='size':
            print(len(q))
        elif question[0]=='empty':
            if len(q)==0:
                print(1)
            else:print(0)
        elif question[0]=='front':
            if len(q)==0:
                print(-1)
            else:
                print(q[0])
        elif question[0]=='back':
            if len(q)==0:
                print(-1)
            else:
                print(q[-1])

기본적으로 큐를 구현하여 푸는 문제이다. 큐의 다양한 기능들을 조건문을 통하여 해결하였다.

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

import sys
input = sys.stdin.readline
from collections import deque

q=deque()
n=int(input())
for i in range(n):
    question = input().split()
    if len(question)==2:
        order=question[0]
        number=question[1]
        if order=='push_front':
            q.appendleft(number)
        elif order=='push_back':
            q.append(number)
    else:
        if question[0]=='pop_front':
            if q:
                print(q.popleft())
            else:
                print(-1)
        elif question[0]=='pop_back':
            if q:
                print(q.pop())
            else:
                print(-1)
        elif question[0]=='size':
            print(len(q))
        elif question[0]=='empty':
            if q:
                print(0)
            else:
                print(1)
        elif question[0]=='front':
            if q:
                print(q[0])
            else:
                print(-1)
        elif question[0]=='back':
            if q:
                print(q[-1])
            else:
                print(-1)

10845와 같이 deque를 사용하여서 문제를 해결하였다.

위에 두 문제에서 핵심은 input()대신 sys.stdin.readline()을 사용하여야 된다는 것이다.

반복문으로 여러줄을 입력 받아야 할 때 input()은 시간초과를 일으킬 수 있다.

# ) sys.stdin.readline()은 한줄 단위로 입력받기 때문에, enter가 같이 입력이된다.

# ) strip()은 문자열 맨 앞과 맨 끝의 공백문자를 제거한다.

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

[문제 풀이]

이 문제는 위에 두 문제와 비슷하다고 생각하고 쉽게 풀려고 했는데 잘 풀리지 않았다. 먼저 위에 두 문제처럼 풀었다.

from collections import deque
import sys
input = sys.stdin.readline
q=deque()
str = input()
for i in range(len(str)):
    q.append(str[i])
m=int(input())
cursor=len(q)
for i in range(m):
    question=input().split()
    if len(question)==2:
        number=question[1]
        q.insert(cursor,number)
        cursor+=1
    else:
        if question[0]=='L':
            if cursor!=0:
                cursor-=1
        elif question[0]=='D':
            if cursor!=len(q):
                cursor+=1
        elif question[0]=='B':
            if cursor!=0:
                q = list(q)
                q.pop(cursor-1)
                q=deque(q)
                cursor-=1
for i in range(len(q)):
    print(q[i],end='')

위에 방식대로 풀려고 했는데 시간초과, 런타임에러(TypeError)같은 에러가 계속 났다. 시간 초과를 해결하는 것이 이 문제의 핵심이라 생각했다. 문제를 보면 시간제한이 다른 문제보다 적다.

input도 sys.stdin.readline으로 바꿔도 보고, 내가 할 수 있는 일들을 해봤지만 시간초과는 계속 났다. 그리고 입력 부분을 다시 봤다.

내가 푼 방식으로는 문자열의 길이가 N일때 O(N)의 시간복잡도가 발생한다. 그렇다면 최악의 경우 100,000길이인 문자열을 500,000번 다루면 100,000 X 500,000 번의 연산이 필요하게 된다. M을 줄이기보다 문자열 통째로 연산하는 것을 부분적으로 할 수 있도록 줄여봐야 된다고 생각했다.

https://bnzn2426.tistory.com/112

여기서 많은 도움을 받게 되었다. 

두 개의 스택을 이용해 커서의 앞 부분과 커서의 뒷 부분을 구분하여 생각한다.

먼저 첫번째 스택에 모두 들어가고 두번째 스택은 비어있다. 만약 L을 입력받아 커서가 왼쪽으로 움직인다면 첫번째 스택은 pop을 통해 꺼내고 두번째 스택에 push되는 것이다. 

반대로 D를 입력받으면 첫번째 스택에 push, 두번째 스택에서 pop을 하는 것이다. 

from sys import stdin
input = stdin.readline
first = list(stdin.readline().strip())
second = []
m= int(input())
for i in range(m):
    question=input().split()
    if question[0]=='L':
        if first: #첫번째 스택이 존재할때 (없으면 더 왼쪽으로 커서가 못가니까)
            second.append(first.pop())
    elif question[0]=='D':
        if second:
            first.append(second.pop())
    elif question[0]=='B':
        if first:
            first.pop()
    elif question[0]=='P':
        first.append(question[1])
print("".join(first+list(reversed(second))))