[BOJ] 5430 AC (python)

문제

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

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

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

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

입력

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

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

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

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

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

출력

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

풀이

두가지 방법으로 풀어봤다.
첫번째 방법은 index를 사용하는 방법이다. list에서 pop이나 slicing, reverse를 반복해서 사용하다보면 시간복잡도가 크게 증가하기 때문에 최대한 이를 사용하지 않고자 생각한 방법이다.
우선 R이 홀수번 등장한 상태에서 D가 등장하면 list의 뒤에서부터 하나씩 없애고, 짝수번 등장한 상태라면 list의 앞에서부터 하나씩 없애기 때문에 R의 등장 횟수 홀짝 여부를 확인하기 위한 flip변수와 앞,뒤에서 하나씩 줄여나가 한번에 slicing하기 위한 start, end 변수를 설정했다.
flip에 따라 앞 혹은 뒤에서 index를 하나씩 줄여나가고 마지막에 딱 한번 slicing하고 R이 짝수번 등장하면 list를 뒤집어서 출력한다.

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    p = list(sys.stdin.readline().strip())
    n = int(sys.stdin.readline())
    nums = eval(sys.stdin.readline().strip())
    
    flip = 0
    start, end = 0, n
    if p.count('D') > n:
        print('error')
    else:
        for func in p:
            if func == "R":
                flip = (flip+1)%2
            else:
                if flip:
                    end -= 1
                else:
                    start += 1
        nums = nums[start:end]
        if flip:
            print('[' + ','.join(list(map(str,nums[::-1])))+']')
        else:
            print('[' + ','.join(list(map(str,nums)))+']')

두번째 방법은 deque를 사용하는 방식이다.
deque를 쓰더라도 flip을 사용하는 것은 마찬가지다. 안쓰고 해보려니까 시간초과가 나더라...
첫번째 방법과 마찬가지로 flip에 따라서 앞에서부터 하나씩 지워나갈지(popleft()), 뒤에서부터 지워나갈지(pop()) 결정하고 마지막에 flip에 따라 한번 뒤집고 출력한다.

import sys
from collections import deque

T = int(sys.stdin.readline())

for _ in range(T):
    p = list(sys.stdin.readline().strip())
    n = int(sys.stdin.readline())
    nums = deque(eval(sys.stdin.readline().strip()))

    flip = 0

    if p.count('D') > n:
        print('error')
    else:
        for func in p:
            if func == "R":
                flip = (flip+1)%2
            else:
                if flip:
                    nums.pop()
                else:
                    nums.popleft()
        if flip:
            nums = list(nums)[::-1]
        print('[' + ','.join(list(map(str,nums)))+']')

사실 다른 부분은 index를 이용해 딱 한번 slicing을 하는지, deque를 써서 pop에 걸리는 시간을 줄이는가 차이이다.

위가 deque, 아래가 index다. 소요 시간과 메모리 사용량은 근소하게 index가 조금 더 좋다.
편한거 쓰면 될 것 같다.