[python] 백준 5430번 : AC (골드 5)

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

해당 문제에서 틀렸던 점은 시간복잡도가 주 원인 이였다.

1. R 명령어를 받을 때 모든 배열을 뒤집어 주면 O(N)의 시간 복잡도가 발생하므로 시간 초과가 발생하게 된다.

이를 해결하려면 R 명령을 받을때마다 배열을 뒤집어 주지 않고 현재 상태가 정상적인 상태인지 뒤집어진 상태인지만 표시하면 된다. 뒤집어진 상태에서 D 명령을 받으면 뒤에서 빼주고 정상적인 상태라면 앞에서 빼주면 된다. (

2. list 의 경우 앞에 있는 인덱스의 값을 제거할 경우 이 또한 시간 복잡도가 많이 발생하므로 큐로 해주어야 한다.

3. 출력 또한 배열로 되어있지만 배열로 출력을 하면 오류가 난다. str형식으로 배열 형태를 갖추어서 출력해주어야 한다.

import collections 
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    result = True
    number = collections.deque()
    stack = list()
    command = list(input().rstrip())
    n = int(input().rstrip())
    arr = input().rstrip()
    if n:
        arr = arr[1:-1].split(',')
        for i in arr:
            number.append(int(i))
    reverse = False
    for com in command:
        # R 명령어를 받을떄마다 모든 배열을 뒤집어주면 많은 O(N) 의 복잡도가 발생하므로 현재 상태가 뒤집어져 있는 상태인지 아닌지만 바꿔준다
        if com == 'R':
            if reverse:
                reverse = False
            else:
                reverse = True
        # 배열이 뒤집어져 있을경우 맨 뒤에서 빼주고, 그대로일 경우 앞에서 빼준다.
        elif com == 'D':
            if len(number) == 0:
                result = False
                break
            elif reverse:
                number.pop()
            else:
                number.popleft()

    if result:
        if reverse:
        # deque 의 경우 reverse 함수를 사용할 경우 내림차순 정렬이 아닌 순서만 뒤집어 준다.
            number.reverse()
        # 출력은 리스트가 아닌 str 형식으로 해야함.
        print('[' + ','.join(map(str, number)) + ']')
    else:
        print('error')