[백준] AC(5430) - 파이썬(Python)

🔗 문제 링크

---

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

 

문제 설명

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

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

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

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

입력

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

- 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

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

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

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

출력

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

 

✨ 풀이 과정

---

✅ 문제 접근 방법

처음에는 덱을 사용해야겠다는 아이디어가 번뜩 떠오르지 않아서 큐를 사용하여서 문제의 지문대로 풀어나갔습니다.

# 테스트 케이스의 갯수
T=int(input())

# 입력받기
for _ in range(T):
    # 수행할 함수 입력
    p=input()
    # 배열에 들어있는 수의 갯수
    n=int(input())
    # 배열 입력
    arr=input().strip()[1:-1].split(",")
    for command in p:
        if command=="R":
            if not arr:
                break
            if arr:
                arr.reverse()
        elif command=="D":
            if not arr:
                break
            if arr:
                arr.pop(0)
    if not arr:
        print("error")
    if arr:
        print("["+ ",".join(arr)+"]")

그랬더니 `reverse()`와 `pop(0)` 작업이 리스트에서 반복적으로 호출될 때 이 두 작업은 각각 O(n)의 시간 복잡도를 가지므로, 리스트가 커지면 성능이 급격히 저하되어서 시간초과가 발생할 수 있다는 것을 알게 되었습니다. 이 코드를 제출했더니 역시 예상대로 시간초과가 발생했습니다.

 

그 후, 지문을 다시 천천히 읽고 나서는 주어진 명령어를 순차적으로 처리하면서 배열을 조작해야 한다는 것을 파악했습니다 ! 배열의 순서를 뒤집는 연산이 빈번하게 발생할 수 있으므로, 효율적인 데이터 자료구조를 사용하여 문제를 해결해야겠다고 생각했습니다. 따라서 `덱(deque)`을 사용하면 양쪽에서의 삽입과 삭제가 효율적일 것이라고 판단하고 이를 이용하기로 했습니다.🤔

💡문제 로직
1. 명령어를 순차적으로 처리합니다.
2. 뒤집기 명령어('R')가 나오면 뒤집기 플래그를 반전시킵니다.
3. 버리기 명령어('D')가 나오면 현재 배열 상태에 따라 앞이나 뒤에서 요소를 제거합니다.
4. 명령어 처리가 끝난 후, 최종 상태가 뒤집힌 상태이면 배열을 뒤집어 출력합니다.

 

위의 로직대로 명령어를 순차적으로 처리하면서 각 명령어에 따라 배열을 조작하였습니다. 뒤집기 연산이 자주 발생하므로, 뒤집기 명령어가 나올 때마다 실제로 배열을 뒤집는 대신 뒤집기 여부를 나타내는 플래그를 사용하여 마지막에 필요 시 뒤집도록 하였습니다.

👩‍💻최종 코드

---

import sys
from collections import deque

input = sys.stdin.readline
t = int(input())  

for _ in range(t):
    commands = input().strip()  # 명령어 문자열
    num_elements = int(input())  # 배열의 원소 개수
    elements = input().strip()[1:-1]  # 대괄호를 제거하고 배열 요소를 가져오기

    # 덱 초기화: 빈 문자열이 아니면 쉼표로 구분하여 덱으로 변환
    if elements:
        dq = deque(elements.split(','))
    else:
        dq = deque()

    is_reversed = False  # 배열의 순서를 뒤집었는지 여부를 나타냄
    error_occurred = False  # 오류가 발생했는지를 나타냄

    # 명령어를 순차적으로 처리
    for command in commands:
        if command == 'R':
            # R 명령어가 나오면 뒤집기 플래그를 반전
            is_reversed = not is_reversed
        elif command == 'D':
            # D 명령어 처리
            if not dq:
                # 덱이 비어있으면 에러 출력
                print("error")
                error_occurred = True
                break
            if is_reversed:
                # 뒤집힌 상태에서는 덱의 끝에서 제거
                dq.pop()
            else:
                # 정상 상태에서는 덱의 앞에서 제거
                dq.popleft()

    if error_occurred:
        continue  # 에러가 발생하면 다음 테스트 케이스로 넘어감

    if is_reversed:
        # 최종 상태가 뒤집힌 경우 덱을 뒤집음
        dq.reverse()

    # 덱을 문자열로 변환하여 출력
    print("[" + ",".join(dq) + "]")