[백준 알고리즘] - AC (5430번) with Python

📎 간략한 문제 정리

• 새로운 언어에는 두가지 함수 R(뒤집기), D(버리기)가 있습니다. R은 숫자의 순서를 뒤집는 함수이고 D는 첫번째 숫자를 버리는 함수입니다. 배열이 비어있을 때 D를 사용하면 에러가 발생합니다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하는 문제입니다.

📈 문제 분석

• 함수 명령문을 순회하며 해당 함수를 적용할 수 있습니다. 문제는 R함수는 O(N)인데 이렇게 되면 O(N^2)로 100,000의 범위에서 100억으로 속도 이슈가 발생합니다. 단순히 반복문을 사용하면 문제가 발생합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 우선 명령문에 RR이 연속으로 존재한다면 제거해줄 수 있습니다. 그리고 D의 개수가 전체 숫자의 개수보다 많다면 error가 발생하므로 연산할 필요가 없습니다. 이것을 제거해주고 연산을 해볼 수 있습니다.

💻 풀이한 코드

from sys import stdin
from collections import deque
input = stdin.readline
T = int(input())
result = []
for _ in range(T):
    reversed = False
    function = input().strip()
    n = int(input())
    array = deque(list(input().lstrip('[').rstrip(']\n').split(',')))
    if len(array) < function.count('D') or (array[0] == '' and function.count('D') > 0):
        result.append("error")
        continue
    function = function.replace("RR", "")
    for one_function in function:
        if one_function == "R":
            reversed = False if reversed else True
        elif one_function == "D":
            if reversed:
                array.pop()
            else:
                array.popleft()
    if reversed:
        array.reverse()
    result.append(f"[{','.join(array)}]")
print('\n'.join(result))

📝 해결 과정에서 만난 문제, 고민들

• RR을 제거하는 것 만으로 시간 절약이 충분하지 못했습니다. 테스트 케이스 자체도 O(N)이기 때문에 연산자를 검색하는 순회 for문, for문 안에서 reverse함수까지 구현하면 최대 O(N^3)까지 나오므로 속도가 최악이 됩니다. 포인트는 reverse함수를 구현하지 않는 것입니다.

  [1, 2, 3, 4, 5]의 배열을 stack처럼 마지막 요소만 빼는 구조라고 생각했을 때 요소를 제거하고 전환한 뒤 다시 요소를 제거하는 과정을 보면

  [1, 2, 3, 4] -> [4, 3, 2, 1] -> [4, 3, 2]

  가 됩니다. 이를 다르게 생각해보면 reverse 한 이후 요소 제거는 오른쪽이 아니라 왼쪽에서 제거하면 되는 개념이고, 결과물만 마지막으로 한 번 뒤집어줄지만 결정하면 결과물이 같습니다.

  [1, 2, 3, 4] -> [2, 3, 4] -> [4, 3, 2]

  즉, 각 시점에 reverse가 된 상태인지에 따라 pop(), popleft()를 결정하고 마지막에만 결과물을 reverse할 지 결정하면 됩니다.

  배열을 직접적으로 편집하는 로직의 경우 꼭 그 로직을 실행해야하는지, 개념적으로 더 빠르게 수정할 방법이 있는지 고민해보는 습관이 필요한 것을 배웠습니다.

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