문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x₁,...,x_n]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ x_i ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

풀이 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def process_elements(funcs, elements, is_reversed):
    left, right = 0, len(elements) - 1

    for func in funcs:
        if func == "R":
            is_reversed = not is_reversed
        elif func == "D":
            if is_reversed:
                right -= 1
            else:
                left += 1

    if left > right + 1:
        return "error"
    else:
        result = elements[left : right + 1]
        if is_reversed: result.reverse()

        return "[" + ",".join(map(str, result)) + "]"


def main():
    num_of_tests = int(input())

    for i in range(num_of_tests):
        funcs = input()
        num_of_elements = int(input())
        elements = map(int, input()[1:-1].split(","))
        if num_of_elements != 0:
            elements = list(elements)
        else:
            elements = []

        print(process_elements(funcs, elements, False))


if __name__ == "__main__":
    main()

CHECK!

함수로 나누는 과정에서 변수의 초기값 선언을 대신해줌으로써 코드가 간결해지고 보기 편해짐
deque를 사용했는데, 사용하지 않아도 시간 안에 잘 돌아감 결국 코드를 어떻게 구현하냐의 문제인 것 같음
순서를 매번 뒤집지 않고, R, D 명령에 따라 뒤집혔는지 여부와 각 경우에 따라 어느쪽에서 배열의 요소를 삭제하는지 등을 변수에 저장 한 후, 마지막에 배열을 뒤집거나 slicing하는 작업을 한번만 진행한다. 이러면 time complexity가 적어지는것을 볼 수 있음
time complexity : test case - t, funcs 길이 p, elements 갯수 n 이라고 한다면
O(t * (p+n)) 정도 일 것 같다.
전체 테스트 케이스에 주어지는 p, n의 합은 70만을 넘지 않는다고 했으므로, 결국 t*(p+n) <= 70만
결국 O(1)으로 수렴하게 될 것 같다. 70만을 O(1)이라고 해도 되는지는 잘 모르겠지만…