[백준] 5430 - AC

AC

생각 흐름

1. 연산에 따라 배열을 뒤집고, 배열의 맨 앞 수를 지운다.
2. 명령어마다 시간복잡도를 최소화해야 한다.
3. 맨 앞의 수만 지우므로 배열을 실제로 뒤집을 필요는 없다.
   -> 배열을 뒤집으면 어차피 앞은 뒤가 되고 뒤는 앞이 된다.
4. 앞/뒤에서 삭제를 빨리 할 수 있는 연결 리스트를 사용하자.

사실 알고리즘 문제를 보다보면 각 명령어가 주어졌을 때 해야하는 일을 일러주고
그 명령어가 담긴 문자열 하나를 주고 배열이나 다른 것들을 조작하는 문제가 많다.
그런 문제들은 보통 문자열 길이가 100,000이나 그보다 많기 때문에
한 명령어의 시간복잡도를 최대한 $O(1)$이나 $O(\log N)$ 으로 만드는 것을 중점으로 알고리즘을 설계해야 한다.

풀이

이번 문제 역시 R과 D의 명령어가 등장하는데
배열을 뒤집는 R은 실제로 구현하게 된다면 $O(N)$이 된다.
배열 앞의 원소를 지우는 D 역시 $O(N)$이 된다.

R 함수가 배열을 뒤집는다곤 하지만 그것은 중요하지 않다.
배열을 뒤집으면 어차피 앞은 뒤가 되고 뒤는 앞이 된다.
그래서 R 함수는 사실 빼는 위치의 앞/뒤를 바꾸는 함수이다.

DF라는 변수를 두어 배열의 방향을 표시하고 DF==1이면 앞에서, -1이면 뒤에서 빼자.
R 함수는 DF에 $-1$을 곱하는 $O(1)$ 연산으로 바뀌었다.

D 함수는 앞 혹은 뒤에서 원소 하나를 제거하는 연산이다.
문제에서 말하는 배열을 실제 배열이 아닌 연결 리스트로 구현한다면 이 연산 역시 시간복잡도가 $O(1)$로 바뀐다.

모든 함수의 시간복잡도가 $O(1)$로 구현 가능하니
명령어대로 배열을 조작하고, 해당 배열을 출력하면 정답을 얻을 수 있다.

배열 파싱은 정규식을 이용하였다. 문자열에서 모든 \d+을 뽑아내면 정수 배열이 된다.
뽑힐 때 문자열 자료형으로 뽑히지만 사실 그게 정수형인지 문자열인지는 중요하지 않기 때문에 따로 변환 과정을 거치지 않아도 된다.

코드

import sys
import re
from collections import deque


def solution():
    T = int(sys.stdin.readline())

    for t in range(T):
        sys.stdout.write("%s\n" % tc())


def tc():
    p, arr = get_input()
    df = 1

    for command in p:
        if command == 'R':
            df *= -1
        else:
            if len(arr) == 0:
                return "error"
            if df == 1:
                arr.popleft()
            else:
                arr.pop()

    answer = []
    while len(arr) > 0:
        if df == 1:
            answer.append(arr.popleft())
        else:
            answer.append(arr.pop())

    return '[' + ",".join(answer) + ']'


def get_input():
    p = sys.stdin.readline().strip()
    _ = sys.stdin.readline()
    arr = sys.stdin.readline().strip()
    arr = deque(re.findall("\d+", arr))
    return p, arr


solution()

배열과 연결 리스트에 대해서

배열은 안의 원소가 중요하다. 그래서 randomly accessible 해야 한다.
배열에서 $i$번째 원소를 찾을 때의 시간복잡도는 $O(1)$가 된다.
이런 장점을 취하기 위해 배열의 길이가 변화할 때 추가적인 작업을 감수한다.

배열에선 원소가 삭제될 때 그 뒤의 것들을 왼쪽으로 민다거나
삽입될 때 삽입될 자리의 오른쪽 것들을 한 칸씩 오른쪽으로 미는 방식으로
배열의 순서를 새로 갱신해줘야 한다.
삽입/삭제 시의 시간복잡도가 $O(N)$이나 되는 것은 이것 때문이다.

배열 전체에서 원소들에 대한 순서가 중요하지 않다고 가정한다면,
즉 인덱스를 기준으로 배열의 내부를 탐색하지 않는다면 이야기는 달라진다.
연결 리스트, 스택, 큐 등은 이 특성을 만족하기 위해 설계된 자료구조이다.

위의 자료구조에선 전체 자료에서의 원소의 위치는 더이상 고려되지 않는다.
중요한 것은 최소한의 순서, '자료의 앞과 뒤와의 연결'이다.
이것만을 고려한 채로 자료들을 연결하면 $i$번째 원소를 찾는 것이 $O(N)$의 시간복잡도를 가지겠지만
대신 삽입/삭제 시의 작업은 $O(1)$의 시간복잡도를 가지게 된다.
자료 전체가 아닌 삽입/삭제할 부분의 앞/뒤 순서만 수정해주면 되기 때문이다.