백준 / AC / 5430번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: AC / 5430번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/5430

 

문제 설명

---

나의 풀이

from collections import deque

#  선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다.
#  AC는 정수 배열에 연산을 하기 위해 만든 언어이다.
#  이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
def ac(current_function, n, arr):
    reverse_flag = False  # 뒤집기 여부를 저장하는 플래그
    dq = deque(arr)

    for p in current_function:
        if p == 'R':
            reverse_flag = not reverse_flag  # 뒤집기 여부만 토글
        elif p == 'D':
            if dq:
                if reverse_flag:
                    dq.pop()  # 뒤집힌 상태라면 오른쪽에서 제거
                else:
                    dq.popleft()  # 정방향이라면 왼쪽에서 제거
            else:
                return 'error'  # 빈 deque에서 제거 시도 시 에러

    # 플래그에 따라 결과를 결정
    if reverse_flag:
        dq.reverse()

    # 결과 문자열 생성
    return '[' + ','.join(map(str, dq)) + ']'


def main():
    t = int(input())  # 테스트 케이스 개수
    result = []

    for _ in range(t):
        p = list(input())  # 수행할 함수 p
        n = int(input())  # 배열에 들어있는 수의 개수 n

        # 배열에 들어갈 숫자들 처리
        arr_input = input().strip("[]").strip()
        arr = list(map(int, arr_input.split(","))) if arr_input else []

        result.append(ac(p, n, arr))

    # 결과 값 출력
    for res in result:
        print(res)

main()

---

※ 알아야 할 것

시간초과 코드 원인은 다음과 같았습니다.

dq = deque(arr)  # 덱으로 만들어서 사용

    for p in current_fucntion:
        if p == 'R':
            if dq:
                dq = deque(reversed(dq))  # deque 좌우 반전
            else:
                return 'error'
        elif p == 'D':
            if dq:
                dq.popleft()  # 왼쪽부터 하나씩 버린다.
            else:
                return 'error'

덱으로 만들었지만 'R' 처리 과정에서 리스트로 바꾸고 다시 덱으로 만드는 과정에서 시간 복잡도가 초과했습니다.