[백준BOJ] 단계별로 문제풀기 - 큐, 덱 정답 및 후기(파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 큐, 덱 1번~7번을 파이썬으로 풀어보았다. 스택 6문제 모두 깃허브에 올려놓았다. 스택, 큐, 덱을 풀면서 파이썬의 리스트는 매우 편리하며 보다 더 잘 다룰 수 있게 된 것 같다.

 

www.acmicpc.net/step/12

큐, 덱 단계

원본 코드는 깃허브에!!

 

tomy9729/Algorithm

 

 

0. 큐와 덱

큐는 스택과 마찬가지로 대표적인 자료구조 중 하나이다. 스택과 다르게 First-In-First-Out인 선입 선출의 구조를 가지고 있다. queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 한다. 줄에 가장 먼저 선 사람이 표를 먼저 사고 줄을 이탈한다. 그것이 바로 큐의 체계이다. 

스택과 마찬가지로 큐에 데이터를 넣는 것을 enqueue, 데이터를 삭제하는 것은 dequeue이라고 한다. 단 데이터를 넣는 위치와 삭제하는 위치가 다르다. 큐의 가장 먼저 들어온 데이터(가장 앞에 있는 데이터)를 front라고 하며 front는 dequeue을 하는 위치다. 큐의 가장 늦게 들어온 데이터(가장 뒤에 있는 데이터)를 rear라고 하며 enqueue를 하는 위치다.

큐에는 선형큐와 원형 큐가 있다. 메모리가 어느 정도 찬 배열로 만든 큐가 있다고 가정해보자. front에서 dequeue를 수행하여 앞쪽 배열의 메모리는 비어져있다. 그러나 enqueue는 rear에서만 수행하기 때문에 메모리가 남아 있음에도 오버플로우가 발생할 수 있다. 이러한 단점을 보완하기 위해 원형 큐가 생겼다. rear 다음 위치에 front가 오도록 하여 낭비되는 메모리가 없도록 만든 자료구조이다.

문제에 따라서 선형큐가 더 유용할 수도 있고 원형 큐가 더 유용할 수도 있다. 상황에 맞춰 적절한 자료구조를 선택해야 한다. 특히 파이썬의 경우 list의 메소드 기능이 효과적이어서 선형 큐만 사용하더라도 원형 큐의 장점을 유사하게 따라 할 수 있다. 또한 스택과 마찬가지로 연결 리스트 또는 배열로 구현할 수 있다. 

 

 

덱은 double-ended queue의 줄임말로써, 앞과 뒤에서 모두 넣고 뺄 수 있는 자료구조이다. 양방향 큐라고 생각하면 이해하기 편하다. 덱은 스택과 큐의 특성을 모두 갖는 자료구조이다. 덱은 다음 네 가지 기능을 필수로 가능해야한다.

• 앞에서 삽입
• 앞에서 삭제
• 뒤에서 삽입
• 뒤에서 삭제

스택, 큐와 마찬가지로 배열로 구현할 수 있으나, 양방향 연결 리스트를 기반으로 구현하는 경우가 많다. 물론 이번 포스트에서 나오는 문제들을 풀 때는 전부 배열로 구현하여 문제를 해결했다. 

---

 

1. 18258번 큐 2

문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

배열로 큐를 구현한다. front와 back을 선언해주며 초기 값은 각각 0과 1이다. 즉 큐가 비어있을 때 front와 back의 차는 -1이다. 또한 배열에 접근할 수 있는 방법은 오로지 front와 back 뿐이다.

push는 파이썬 리스트의 append 메소드로 구현할 수 있다. 원래 배열로 큐를 구현하면 배열의 크기가 고정적이라는 것이 단점이지만 파이썬의 리스트는 그러한 단점을 극복할 수 있다.

pop은 큐의 front 원소를 출력해주고 front의 크기를 1만큼 증가시켜주면 된다. 큐에는 오로지 front와 back으로만 접근 가능하기 때문에 front를 증가시키면 front보다 앞에 있는 원소들은 사용할 수 없다.

size는 큐에 들어있는 정수의 개수를 출력해야 한다. 큐에는 front부터 back까지의 원소들이 존재하면 back에서 front를 빼고 1을 더한 만큼 존재한다. 

empty는 큐가 빈 상태인지 확인하는 메소드이다. 앞서 말했듯이 front와 back의 차이가 -1이라면 빈 큐이다. 

front와 back을 출력하는 명령은 큐에서 queue[front]와 queue[back]을 출력하면 된다. 

#18258번 큐 2
import sys
input = sys.stdin.readline

n = int(input())
queue = []
front = 0
back = -1
for i in range(n) : 
  command = input()[:-1] # sys.stdin.readline는 개행까지 포함한 문자열을 넘겨준다. 마지막 개행문자를 삭제
  if command[0:4] == 'push' : #push X: 정수 X를 큐에 넣는 연산이다.
    queue.append(int(command[5:]))
    back += 1 
  elif command == 'pop' : #pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if back - front == -1 : 
      print(-1)
    else : 
      print(queue[front])
      front+=1
  elif command == 'size' : 
    print(back-front+1) #size: 큐에 들어있는 정수의 개수를 출력한다.
  elif command == 'empty' :  #empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
    if back - front == -1 : 
      print(1)
    else : 
      print(0)
  elif command == 'front' : #front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if back-front == -1 : 
      print(-1)
    else : 
      print(queue[front])
  elif command == 'back' : #back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if back-front == -1 : 
      print(-1)
    else : 
      print(queue[back])
  else : 
    continue

---

 

 

2. 2164번 카드 2

문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

큐에는 1부터 N까지 오름차순으로 숫자가 삽입되어 있다. 다음 세 가지 동작을 반복한다. 

• 제일 앞에 있는 숫자 삭제
• 그다음 숫자 삭제
• 삭제 한 숫자를 다시 큐에 삽입

위 과정을 큐에 숫자가 한 개만 남을 때까지 반복하면 된다. 즉 front와 back의 차이가 0이 될 때까지 반복한다. 

#2164번 카드2
n = int(input())
nums = [] #큐 
for i in range(n):
  nums.append(i+1)
front = 0 
back = n-1 

while back - front != 0 : # 큐의 길이가 1이 될 때까지
  front += 1 #맨 앞 숫자 삭제
  nums.append(nums[front]) # 맨 앞 숫자 맨 뒤로
  front += 1
  back += 1

print(nums[front])

---

 

 

3. 11866번 요세푸스 문제 0

문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

문제의 시작부터 원이 나온다. 왠지 모르게 원형 큐로 풀어야만 할 것 같지만 선형 큐로 푸는게 더 유용할 것 같아서 선형큐로 풀었다. 앞선 2번 문제와 매우 유사한 문제이다. 

큐에는 1부터 N까지 오름차순으로 숫자가 삽입되어 있다. K번 째 사람을 제거하며, 제거 후 원을 따라서 그다음 k번 째 사람을 제거한다. 이 과정을 모든 사람이 제거될 때까지 반복한다. 만약 K=3이라고 가정한다면 다음 동작을 반복한다.

• 큐에서 1번째 사람 삭제 및 삽입
• 큐에서 2번째 사람 삭제 및 삽입
• 큐에서 3번째 사람 삭제
• 큐에서 4번째 사람 삭제 및 삽입...

즉 정수 K에 대해서 K-1개의 숫자들은 큐의 앞에서 삭제한 후 다시 큐의 뒤로 삽입한다. K번 째 숫자들은 삭제만 진행한다. 그렇게 삭제된 K번 째 숫자들은 따로 배열에 저장하며 빈 큐가 될 때까지 반복한다. 

#11866번 요세푸스 문제 0
n,k = map(int,input().split())
nums = []
for i in range(n) : 
  nums.append(i+1)
result = []
front = 0
back = n-1

while back - front != -1 :
  for i in range(k-1) : #k만큼 앞에 있는 숫자를 뒤로 보냄
    nums.append(nums[front])
    front += 1
    back += 1
  result.append(nums[front]) #k번째마다 저장하고 큐에서 삭제
  front += 1

print("<",end='')
for i in range(n-1) : 
  print(result[i],end='')
  print(", ",end='')
print("%d>"%result[n-1])

---

 

 

4. 1966번 프린터 큐

문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

이번에는 원형 큐를 사용했다. 선형 큐로도 문제를 해결할 수 있지만 원형 큐도 익숙해질 겸 원형 큐로 문제를 풀어보고 싶었다.

큐에는 각 문서의 중요도를 저장하며 어떤 문서가 몇 번째로 인쇄되는지 알아내야 한다. 만약 모든 문서의 중요도가 전부 다르다면 당연하게도 중요도를 오름차순으로 정렬했을 때 알아내고자 하는 문서의 위치가 인쇄 순서가 된다. 하지만 중요도가 같을 경우 큐에 저장되어있는 순서에 따라 인쇄 순서가 결정된다. 때문에 알아내고자 하는 문서의 순서가 정확히 어디 있는지 알고 있어야 한다. 

문서의 인쇄 순서를 나타내는 count 변수를 선언하고 문서가 인쇄될 때마다, 즉 큐에서 삭제가 발생할 때마다 count를 1씩 증가시킨다. 큐의 front가 가장 높은 중요도라면 바로 dequeue를 수행한다. 이때 삭제한 문서가 만약 순서를 알아내고자 하는 문서라면 반복을 종료하고 count를 출력한다. 만약 큐의 front가 가장 높은 중요도가 아니라면 dequeue 후 다시 큐에 enqueue를 수행하며, 만약 이 문서가 순서를 알아내고자 하는 문서라면 문서의 위치인 m을 재설정한다. 또한 원형 큐이기 때문에 삭제와 삽입이 발생할 때마다 front와 back의 변화도 정확히 설정해준다.

#1966번 프린터 큐
t = int(input()) # 테스트케이스 개수

for i in range(t) : 
  n,m = map(int,input().split()) 
  importance = list(map(int,input().split())) # 바로 원형큐로 사용
  importance.append(0)
  front = 0
  back = n
  count = 0
  while back != front : # 원형큐가 비어질 때 까지
    if importance[front] == max(importance) : # 첫 원소가 최댓값이라면
      count += 1 # 카운트 추가
      if front == m : # m이라면
        print(count) # count 출력
        break # while문 종료
      importance[front] = 0 # m이 아닐경우 삭제만 함
      front = (front+1) % len(importance) 
    else : # 첫 원소가 최댓값이 아니라면
      importance[back] = importance[front] # 첫 원소를 마지막 원소로 삽입
      importance[front] = 0 
      if front == m : # 만약 m이 었다면
        m = back # m 재설정
      front = (front+1)%len(importance) 
      back = (back+1)%len(importance) 

---

 

 

5. 10866번 덱

문제
정수를 저장하는 덱(Deque)을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
push_front X: 정수 X를 덱의 앞에 넣는다.
push_back X: 정수 X를 덱의 뒤에 넣는다.
pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 덱에 들어있는 정수의 개수를 출력한다.
empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

1번 문제에서 몇 가지 기능만 더 추가하면 된다. 전부 파이썬 리스트의 메서드를 통해 구현할 수 있다.

리스트의 마지막에 원소를 삽입할 때는 append를 사용했다. insert를 통해 리스트의 처음에 원소를 삽입할 수 있다.

덱의 맨 앞과 뒤에서의 삭제는 pop을 통해 구현할 수 있다.

#10866번 덱
import sys
input = sys.stdin.readline

n = int(input())
deque = []

for i in range(n) : 
  command = input()[:-1] # sys.stdin.readline는 개행까지 포함한 문자열을 넘겨준다. 마지막 개행문자를 삭제
  if command[0:10] == 'push_front' : #push_front X: 정수 X를 덱의 앞에 넣는다.
    deque.insert(0,int(command[11:]))
   
  elif command[0:9] == 'push_back' : #push_back X: 정수 X를 덱의 뒤에 넣는다.
    deque.append(int(command[10:]))
   
  elif command == 'pop_front' : #pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if len(deque) == 0 : 
      print(-1)
    else : 
      print(deque[0])
      deque.pop(0)
  elif command == 'pop_back' : #pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if len(deque) == 0 : 
      print(-1)
    else : 
      print(deque[len(deque)-1])
      deque.pop()
  elif command == 'size' : 
    print(len(deque)) #size: 덱에 들어있는 정수의 개수를 출력한다.
  elif command == 'empty' :  #empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
    if len(deque) == 0 : 
      print(1)
    else : 
      print(0)
  elif command == 'front' : #front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if len(deque) == 0 : 
      print(-1)
    else : 
      print(deque[0])
  elif command == 'back' : #back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    if len(deque) == 0 : 
      print(-1)
    else : 
      print(deque[len(deque)-1])
  else : 
    continue

---

 

 

6. 1021번 회전하는 큐

문제
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

문제에서 말하는 양방향 순화 큐가 덱이다. 문제에 나와있는 세 가지 연산을 풀이하면 다음과 같다. 

1. 덱의 맨 앞에 있는 원소를 삭제한다.
2. 덱의 맨 앞에 있는 원소를 삭제하고 덱의 맨 뒤로 삽입한다.
3. 덱의 맨 뒤에 있는 원소를 삭제하고 덱의 맨 앞으로 삽입한다.

큐의 크기 N에서 M개의 수를 삭제할 예정이며 다음으로 뽑고자 하는 수의 위치가 순서대로 주어진다. 큐의 크기와 위치가 주어지므로 그 자체를 큐의 원소로 보면 된다. 예를 들어서 N=10, M=3이 주어지고 뽑아내려고 하는 수의 위치가 1,2,3이라면 1부터 10까지 순서대로 저장되어있는 큐에서 1,2,3을 순서대로 삭제하는 것이다. 큐에서 삭제하는 연산은 1번뿐이며 2번 또는 3번 연산을 통해 삭제하고자 하는 숫자를 큐의 제일 앞으로 보내야 한다. 이때 2,3번 연산을 최소 사용 횟수를 구하는 것이 문제이다. 

큐에 1부터 10까지 오름차순으로 저장되어 있고 숫자 3을 삭제한다고 가정해보자. 3을 제일 앞으로 보내기 위해서는 2번 연산을 두 번 수행해야 하며, 이때가 최소 사용 횟수이다. 모든 경우에서 어떤 숫자를 큐의 맨 앞에 보낼 때 연산의 최소 사용 횟수는 2번 연산만 사용하거나, 3번 연산만 사용하는 것이며 2번 연산과 3번 연산을 함께 사용하면 결코 최소 사용 횟수가 될 수 없다. 

두 개의 함수 left와 right를 만든다. left함수는 2번 연산만 사용했을 때 특정 숫자가 큐의 맨 앞에 올 때까지 사용하는 연산의 횟수이다. right함수는 3번 연산만 사용하여 특정 숫자가 큐의 맨 앞에 올 때까지 사용하는 연산의 횟수이다. 뽑고자 하는 모든 수에 대하여 left와 right를 함수를 통해 뽑고자 하는 수를 큐의 맨 앞에 오고 각 사용 횟수 중 더 적은 횟수를 사용한 연산을 선택한다. 각 경우에서 최소 사용 횟수를 모두 더한 사용 횟수가 문제에서 요구하는 최솟값이다. 

#1021번 회전하는 큐
n,m = map(int,input().split())
result = list(map(int,input().split()))
deque = list(range(1,n+1))
count = 0

def left(d, r, i): # 2번 내용
  c = 0
  d = list(d)
  while d[0] != r[i] : 
    d.append(d[0])
    d.pop(0)
    c += 1
  d.pop(0)
  return d, c

def right(d, r, i): # 3번 내용
  c = 0
  d = list(d)
  while d[0] != r[i] : 
    d.insert(0,d[len(d)-1])
    d.pop()
    c += 1
  d.pop(0)
  return d, c

for i in range(m) :
  deque1, count1 = left(tuple(deque),result,i) # deque를 보존하기위해 tuple로 넘겨준다
  deque2, count2 = right(tuple(deque),result,i)
  if count1 < count2 : # count가 더 적은 것으로 결정
    deque = deque1
    count += count1
  else :
    deque = deque2
    count += count2

print(count)

---

 

 

7. 5430번 AC

문제
선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.
배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

시간적 제약이 없다면 쉬운 문제이다. 함수 R에 대해서 실제로 배열을 뒤집으면 되기 때문이다. 그러나 R을 수행할 때마다 배열을 뒤집으면 시간이 너무 오래 걸린다. 때문에 덱을 통해 뒤집은 것과 같은 결과를 보이게 해야 한다. 

연산은 'R'과 'D'로만 이루어져 있으며 R은 배열을 뒤집고 D는 배열 맨 앞의 숫자를 삭제한다. 연산을 R을 기준으로 나눠준다. 예를 들어 연산이 'DDRDRDDRRD'라면 ['DD', 'D', 'DD', '', 'D']처럼 말이다. 연산을 R로 나눈 배열을 P라고 하자. 이렇게 되면 P의 짝수 위치에 있는 D는 원래 배열에서 맨 앞의 숫자를 삭제하는 것이고, 홀수 위치에 있는 D는 뒤집은 배열의 맨 앞의 숫자를 삭제하는 것이다. 배열을 덱이라고 생각해보자. 짝수 위치의 D는 덱의 맨 앞에서 삭제하는 것이고 홀수 위치의 D는 덱의 맨 뒤에서 삭제하는 것이다. 짝수 위치마다 있는 D의 개수만큼 덱의 앞에서 삭제하고, 홀수 위치마다 있는 D의 개수만큼 덱의 뒤에서 삭제한다. 

마지막으로 배열이 최종적으로 역순인지 아닌지를 알아야 한다. 이를 알기 위해서는 연산에서 R이 몇번 나왔는지 알아야한다. P는 연산을 R을 기준으로 나눈 D들의 집합이다. 즉 P의 길이가 짝수라면 R은 홀수번 나온 것이며, P의 길이가 홀수라면 R은 짝수번 나온 것이다. R이 홀수번 나오면 배열은 역순이며 R이 짝수번 나오면 배열은 정순이다. 

#5430번 AC
t = int(input())
for i in range(t) : 
  p = input()
  n = int(input())
  nums = input() #덱
  p = list(map(str,p.split("R"))) # R을 기준으로 문자열을 나눠줌
  if len(nums) == 2 : # 만약 빈 배열일 경우 따로 초기화
    nums = []
  else :
    nums = list(map(int,nums[1:-1].split(','))) # 입력받은 문자열을 괄호는 빼고 콤마를 기준으로 나눠줌
  front = 0 
  back = len(nums)-1
  error = 0

  for j in range(len(p)) : # R을 기준으로 나눈 p, 즉 D로만 구성되어 있음
    if j % 2 == 0 :
      front += len(p[j]) # 짝수번 째 D들은 front에 더해주고
    else : 
      back -= len(p[j]) # 홀수번 째 D들은 back에서 빼준다
    if back - front < -1 : #만약 배열이 비었는데도 삭제를 시도하면 에러처리함
      error = 1 
      break
  nums = nums[front:back+1]
  if len(p) % 2 == 0 : # R이 홀수 개라면 p의 길이는 짝수, R이 짝수 개라면 p의 길이는 홀수이다.
    nums = list(reversed(nums)) # p의 길이가 짝수라면 R은 홀수이므로 최종적으로 배열은 역순이 된다.
    
  if error == 1 :
    print("error")
  else :
    if len(nums) == 0 : #덱이 빈 경우
      print("[]")
    else :
      print("[%d"%nums[0],end='')
      for j in range(1,len(nums)) : 
        print(",%d"%nums[j],end='')
      print("]")