[BOJ] #5430 AC (Python, Deque, 시간 초과 해결)

🌱 문제

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

 

🌱 풀이

1. 입력 받기

T = int(input())

for _ in range(T):
    p = input()
    p.replace("RR", "")
    p = list(p)
    n = int(input())
    array = deque(eval(input()))

• 테스트 케이스 개수인 T를 int로 받아서 해당 개수만큼 반복문을 들어갑니다.
• 수행해야할 함수 p는 우선 string으로 받습니다. 이때, RR은 뒤집고 바로 뒤집기 때문에 배열에 아무런 변화를 주지 않으므로 replace()함수로 바로 지웠습니다. 그리고나서 string을 list로 바꾸어 이후에 반복문을 수행하며 함수 하나하나를 탐색할 수 있도록 하였습니다. 
• 가장 고민이 되었던 부분은 배열(array)을 입력받는 부분이었는데, 배열이 "1 2 3 4" 이런식으로 입력되는 것이 아니라 "[1,2,3,4]" 이렇게 리스트로 보이는 문자열로 입력되기 때문에 문자열 처리를 하여 실제 리스트 형태로 입력을 받아야 합니다. 처음에는 `,`로 split()함수를 써서 문자열을 처리하려고 하였지만, eval() 함수로 간단하게 처리할 수 있었습니다. eval()함수는 파이썬에서 문자열로 표현된 표현식을 실행하고 결과를 반환하는 함수입니다. 따라서 string으로 입력받은 "[1,2,3,4]"를 리스트로 판단하여 바로 리스트로 판단합니다. 그리고나서 덱으로 문제를 풀어야하기 때문에 deque()로 다시 자료형을 바꾸어주었습니다.

2. 무조건 error가 출력되는 상황 먼저 판단하기

if p.count("D") > len(array):
    print("error")
    continue

D의 개수가 배열의 전체 길이보다 많다면 당연히 error가 출력되야할 것입니다. 따라서 반복문 들어가기 전에 이 경우를 검사한다. erorr라면 continue로 이후 반복문을 들어가지 않도록 합니다.

 

3. 덱을 사용하여 구현하기

일단 부끄럽지만 나의 삽질... 역시나 이 문제는 빡쎈 시간 제한을 해결해야 풀 수 있는 문제입니다. 

우선 로직은, 배열을 뒤집어야할 때마다 reverse() 함수나 array[::-1]처럼 슬라이싱으로 뒤집는다면 연산마다 $O(N)$의 시간복잡도로 연산이 되기 때문에 무조건 시간초과가 납니다. 따라서 방향을 저장하고 있는 flag를 만들어서 뒤집을 때마다 그 flag의 값만 바꾸고 뒤집는 연산은 마지막에 한번만 수행할 수 있도록 합니다.

direction = 1
for f in p:
    if f == 'R':
        direction *= -1
    elif f == 'D':
        if len(array) == 0:
            print("error")
            break
        if direction == 1:
            array.popleft()
            # array = array[1:]
        else:
            array.pop()
            # array = array[:-1]
if direction == -1:
    array.reverse()

• 방향을 저장하는 flag이 direction을 처음에는 1로 설정합니다. 
• 수행해야 할 함수들이 담겨있는 p에서 함수들을 하나씩 꺼내면서 R일 때는 방향의 부호만 바꾸어줍니다. D일 때는 방향을 보고 정방향일 때는 앞에서 꺼내고(popleft()), 역방향일 때는 뒤에서 꺼냅니다(pop()).
• 이때, 원소를 제거하는 방법에서 시간복잡도의 차이가 있습니다. 만약 array를 리스트 자료형으로 두고 슬라이싱(list = list[1:])으로 제거한다면 시간복잡도는 $O(N)$ 이지만 덱(deque)에서 popleft()나 pop() 함수를 사용하여 원소를 제거하면 시간복잡도가 $O(1)$ 입니다.
  왜냐하면 리스트에서 슬라이싱을 통해 맨 앞 원소를 제거하는 것은 새 리스트를 생성하고 원소를 복사하기 때문에 비효율적입니다. 반면에 덱에서 맨 앞 원소를 제거하는 것은 매우 효율적이고, 상수 시간에 수행됩니다.
• 함수를 모두 수행한 뒤에 direction이 -1이라면 이때 마지막으로 한번만 reverse() 연산을 수행합니다.

 

4. 결과 출력

print(str(list(array)).replace(' ', ''))

결과 출력 시, [1, 2, 3, 4]가 아닌 blank없이 [1,2,3,4]로 출력되어야하기 때문에 위와 같이 문자열 처리를 한 후, 출력합니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 5430 AC

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    p = input()
    p.replace("RR", "")
    p = list(p)
    n = int(input())
    array = deque(eval(input()))

    if p.count("D") > len(array):
        print("error")
        continue

    direction = 1
    for f in p:
        if f == 'R':
            direction *= -1
        elif f == 'D':
            if len(array) == 0:
                print("error")
                break
            if direction == 1:
                array.popleft()
            else:
                array.pop()
    if direction == -1:
        array.reverse()
    print(str(list(array)).replace(' ', ''))