Medical and Programming Study

역시나 지난번에 푼 문제에 이어서 collections에 있는 deque를 이용하는 문제이다.

이번에는 appendleft()가 추가되었다!

문제의 큰 흐름은 앞서 스택에서 했던 부분과 유사하여 크게 설명하지 않고 늘 그렇듯이 주석으로 남겼다.

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

deque_list = deque()    # collections library 중 deque를 사용하면 queue를 시간 안에 구현 가능
N = int(input())    # command 개수 입력

for _ in range(N):    # command 개수만큼 반복
    command = input().split()    # 줄바꿈 문자를 제외하고 공백을 기준으로 분리
    if command[0] == 'push_front':    # 명령어가 push_front일 경우 deque_list의 가장 처음에 값을 추가
        deque_list.appendleft(int(command[1]))
    elif command[0] == 'push_back':    # 명령어가 push_back인 경우 deque_list의 가장 마지막에 값을 추가
        deque_list.append(int(command[1]))
    elif 'pop' in command[0]:    # 명령어가 pop_front 또는 pop_back인 경우
        if len(deque_list) == 0:    # deque_list가 비어있다면 -1을 출력
            print(-1)
        elif 'front' in command[0]:    # 명령어가 pop_front인 경우 가장 처음 값을 pop
            print(deque_list.popleft())
        else:    # 명령어가 pop_back인 경우 가장 마지막 값을 pop
            print(deque_list.pop())
    elif command[0] == 'size':    # 명령어가 size인 경우 deque_list의 size를 출력
        print(len(deque_list))
    elif command[0] == 'empty':    # 명령어가 empty인 경우
        print(1 if len(deque_list) == 0 else 0)    # deque_list가 빈 값이면 1을 출력하고 아니면 0을 출력
    else:    # 명령어가 front 또는 back일 경우
        if len(deque_list) == 0:    # deque_list가 비어있다면 -1을 출력
            print(-1)
        elif command[0] == 'front':    # 명령어가 front일 경우 가장 처음 값을 출력
            print(deque_list[0])
        else:    # 명령어가 back일 경우 가장 마지막 값을 출력
            print(deque_list[-1])

지난 문제에 이어서 collections에 존재하는 deque를 적극 이용하는 문제였다.

처음에는 deque를 쓰지 않고 해결해볼까 생각했지만, 시간 복잡도나 여러 면에서 deque가 효율적일 것 같아서 처음부터 설계를 deque를 고려하여 진행하였다.

deque에는 rotate라는 기능이 존재했고, 지난 번에도 다뤘던 popleft라는 기능도 존재하여 이를 적절하게 사용하면 될 것이라고 생각했다.

rotate는 deque를 회전시키는 기능으로, 음수를 입력하면 왼쪽으로 회전한다고 한다.

즉, deque([1, 2, 3, 4, 5])가 존재하면 rotate(-1)을 할 경우 deque([2, 3, 4, 5, 1])가 되고, rotate(1)을 할 경우 deque([5, 1, 2, 3, 4])가 된다.

이를 적용하여 코드를 완성하였다. (list comprehension도 적극 이용해보았다!)

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

N, K = map(int, input().split())    # 입력을 받을 때 공백을 기준으로 분리한 후 각각을 int 타입으로 변환
num_list = deque(x for x in range(1, N+1))    # number를 1부터 N까지 담고있는 list 생성
result = []    # 결과를 저장하는 list

for _ in range(N):    # N개의 원소를 모두 꺼내므로 N만큼 반복
    num_list.rotate(-K+1)    # deque에 존재하는 rotate 함수를 이용하여 list 회전 (K번째 index를 꺼내므로 회전은 K-1번만 진행)
    result.append(num_list.popleft())    # 가장 좌측에 있는 값을 pop

print('<' + str(result).strip('[]') + '>')    # 예제 출력에 맞게 결과 출력

앞서 다룬 스택과는 다르게 큐는 LILO ( Last In Last Out )이라는 특징을 가지고 있다.

Last In Last Out은 글자 그대로 나중에 들어온 값이 나중에 나간다는 것이다.

이번에 코드를 짜면서 역시 시간 초과 문제가 발생할 것을 염두하여 collections module에 존재하는 deque를 사용하였다.

처음에 한 번 deque를 써보지 않고 해보려 했지만, 먼저 들어온 값을 내보내는 코드에서 reversed(queue_list).pop()도 불가능했고, queue_list[::-1].pop()을 해도 기존의 list가 변하지 않기에 del이나 remove를 사용해야 해서 결국 시간 복잡도가 증가하기에 ( O(N)으로 증가한다. ) deque를 사용할 수 밖에 없었다.

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

queue_list = deque()    # collections library 중 deque를 사용하면 queue를 시간 안에 구현 가능
M = int(input())    # command 개수 입력

for _ in range(M):    # command 개수만큼 반복
    command = input().split()    # 줄바꿈 문자를 제외하고 공백을 기준으로 분리
    
    if command[0] == 'push':    # 명령어가 push인 경우
        queue_list.append(command[1])    # push 다음에 존재하는 숫자를 queue에 추가
    elif command[0] == 'pop':    # 명령어가 pop인 경우
        if len(queue_list) == 0:    # 빈 queue라면 -1을 출력
            print(-1)
        else:    # 빈 queue가 아니라면 deque에 존재하는 popleft()를 이용하여 가장 처음 들어온 값을 pop
            print(queue_list.popleft())
    elif command[0] == 'size':    # 명령어가 size인 경우 queue의 길이 출력
        print(len(queue_list))
    elif command[0] == 'empty':    # 명령어가 empty인 경우
        if len(queue_list) == 0:    # 빈 queue라면 1 출력
            print(1)
        else:    # 빈 queue가 아니라면 0 출력
            print(0)
    elif command[0] == 'front':    # 명령어가 front인 경우
        if len(queue_list) == 0:    # 빈 queue라면 -1을 출력
            print(-1)
        else:    # 빈 queue가 아니라면 가장 앞에 있는 값 출력
            print(queue_list[0])
    else:    # 명령어가 back인 경우
        if len(queue_list) == 0:    # 빈 queue라면 -1을 출력
            print(-1)
        else:    # 빈 queue가 아니라면 가장 마지막에 있는 값 출력
            print(queue_list[-1])