문제 해석

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

AC (정수 배열에 연산을 하기 위해 만든 언어)

• 함수 2개
  • R: 배열 뒤집기
  • D: 첫 번째 수 버리기
• 조합해서 한 번에 사용 ex) R RDD DRDRD …

→ 배열과 수행 함수가 주어졌을 때, AC의 최종 결과를 구하는 프로그램을 작성하라.

조건

• Test case: 1~100
• 조합된 함수 p의 길이 P: 1~$10^5$
• 배열의 길이 n: 0~$10^5$
• 배열 요소 정수의 길이: 1~100
• P+n ≤ 70*$10^4$

Time limit	Memory limit
1 sec	256 MB

예제

입력

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

출력

[2,1]
error
[1,2,3,5,8]
error

---

문제 풀이

https://testcase.ac/problems/5430

우선 Test case가 최대 100개, 순환해야 할 함수 p의 길이가 최대 $10^5$개 이므로
대략적으로 AC 함수 내에서는 O(n) 정도의 연산(100*$10^5$)이 수행되어져야 할 것이다.
즉, 조합된 함수 p를 순회하는 동안, loop의 내부에선 O(1) 정도의 연산이 수행되어야 한다.

reverse()와 pop(0)는 모두 O(n)의 시간복잡도를 가지므로 다른 방법이 필요하다.
→ deque를 사용한다.

함수 R

• reverse()를 계속 직접 반복하지 않고, bool 변수(이하 rv)로 표시만 해둔다.
• 단, loop가 끝난 후, rv==True라면 직접 reverse()를 해줘야 한다.

함수 D

• rv를 고려해 popleft()와 pop() 중 선택하여 사용한다.
• 단, queue(배열)가 비어있다면 “error”를 리턴해야 한다.

구현 코드

# boj5430 - AC 
# : 정수 배열에 연산을 하기 위해 만든 언어
# 기능: R(뒤집기)과 D(버리기)

from collections import deque 

class Solution:

    def AC(funs, nums):

        rv = False
        dq = deque(nums)

        for f in funs:
            
            if f == 'R':
                rv = not rv
            
            else: # D

                if not dq:
                    return "error"
                
                elif rv:
                    dq.pop()
                else:
                    dq.popleft()
                
        
        result = list(dq)
        
        if rv:
            result.reverse()
            
        return "["+','.join(result)+"]"
    

funs_list = []
nums_list = []

# 1 <= T <= 100
T = int(input())

for _ in range(T):

    funs_list.append(input())
    n = int(input()) #100,000
    input_str = input().strip('[]')

    # empty check
    if n > 0: 
        nums_list.append(list(input_str.split(',')))
    else: 
        nums_list.append([])

for i in range(T):
    print(Solution.AC(funs_list[i], nums_list[i]))

# 1sec -> 100 * 100000
# AC: O(n) 정도 required

# Time complexity
# pop() O(1)
# pop(0) O(n)
# strip O(n)
# reverse O(n)

# 처음 생각: pop()만 써서 reverse를 최대한 줄이자
# 고친 것: deque 사용해서 앞뒤로 pop
# 주의: 출력할 때 배열을 출력하면 틀림, 배열 형태의 문자열 출력

---

• deque, string