[BOJ] 5430. AC

문제

AC (https://www.acmicpc.net/problem/5430)

풀이

1. 초기 접근

• 문제조건 해석
  • 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
    • n <= 100,000 이므로, 최대 O(n log n) 안으로 풀어야한다.
    • 함수 p 내 R,D 에 접근할 때마다, 리스트 연산의 시간복잡도가 O(1) 이어야 한다.
  • 기본적으로 문제조건 및 해야할 일은 직관적이고 간단해보인다.
• 알고리즘
  • 함수 p 가 RDD 로 주어지면, 어찌됐든 R, D, D 식으로 리스트 p를 한 번 탐색은 해야할 터,
    기본 루프로 시간복잡도는 O(n) 이 들어간다.
  • 이제 루프 내 파이썬 리스트 연산을 O(1) 안에 끝내야 하는데, 이 때 파이썬 리스트 연산의 시간복잡도를
    평소에 잘 알고있느냐가 기본이 된다. 모르고 있다면, 지금 구글링해서 찾아보자.
  • D 의 경우, 첫 번째 원소를 pop 해야 하므로, deque로 리스트를 구성하고,
    popleft() 를 사용함으로써 O(1) 만에 끝낼 수 있다.
  • R 은 직관적으로 reversed(list) 를 사용해야 함을 알 수 있다.
    문제는, 이 연산은 시간복잡도가 O(n) 이라는 것이다. 즉 루프문 내 사용할 수 없다.
    따라서 이 R 을 어떻게 처리할거냐가 이 문제의 관건인데, 다시 문제조건을 잘 보자.
  • 우리의 연산은 R 과 D 만 주어진다. 즉 첫 번째 원소를 빼거나, 전체를 뒤집거나다.
    만약 뒤집지 않고도, 뒤집은 효과를 볼 수 있을까? 이 상황에서 특별하게?
  • 일종의 flag 를 두자. 뒤집한 상태를 알 수 있도록.
    만약 현재가 뒤집히지 않은 상태라면, D 가 주어졌을 때, 첫 번째 원소를 빼면 된다.
    만약 현재가 뒤집힌 상태라면, D 가 주어졌을 때, 맨 끝의 원소를 빼면 된다.
  • 마지막으로 루프만 밖에서, 현재가 뒤집힌 상태라면, reversed(list) 로 뒤집어주면 된다.
    D 가 왜 첫 번째 원소만 pop 하도록 주어졌는지, 이제야 그 의도가 보이지 않는가?
• 코드

import sys
from collections import deque
t = int(input())

for _ in range(t):
    p = list(sys.stdin.readline())
    n = int(input())
    x = sys.stdin.readline()

    di = 1
    try:
        if n == 0:
            x = []
        else:
            x = deque(list(map(int, x.strip()[1:-1].split(','))))

        for i in p:
            if i == 'R':
                di *= -1
            elif i == 'D':
                if x:
                    if di == 1:
                        x.popleft()
                    else:
                        x.pop()
                else:
                    raise ValueError
    except ValueError:
        print("error")
    else:
        if di == -1:
            x = reversed(x)
        print("[" + ",".join(list(map(str, x))) + "]")