백준 5430 - AC (Python3)

코드

시간초과

from collections import deque
    
def solution(cmd, n ,arr):
    
    # 정수만 남겨 놓기
    arr = arr.strip('[]').split(',')
    if arr != ['']:
        arr = [int(x) for x in arr]
    else:
        arr = ''

    # D 연산 시 처음 숫자를 버리므로 deque 사용 (popleft())
    q = deque(arr)
    
    while len(cmd) != 0:
        c = cmd.popleft()

        if c == 'R':
            q.reverse()

        if c == 'D':
            if not q:
                print("error")
                return
            
            q.popleft()
    
    print('[', end='')
    
    while q:
        num = q.popleft()
        if len(q) == 0:
            print(num, end='')
        else:
            print(num, end=',')
    
    print(']')
    return
    
# 테스트 케이스 개수
T = int(input())

for _ in range(T):
    cmd = input()

    # 명령이 앞에서부터 차례대로 적용되니까 편하게 deque 사용 (popleft())
    cmd = deque(cmd)
    n = int(input())
    arr = input()
        
    solution(cmd, n, arr)   

정답

from collections import deque
    
def solution(cmd, n ,arr):
    
    # 정수만 남겨 놓기
    arr = arr.strip('[]').split(',')
    if arr != ['']:
        arr = [int(x) for x in arr]
    else:
        arr = ''

    # D 연산 시 처음 숫자를 버리므로 deque 사용 (popleft())
    q = deque(arr)
    
    # reverse() 메소드 대신
    # 뒤집기를 해야하는지 판단할 boolean 선언
    check_rev = False
    
    while len(cmd) != 0:
        
        c = cmd.popleft()

        if c == 'R':
            # q.reverse()
            # R이 홀수번 나오면 뒤집기 해야하고
            # 짝수번 나오면 뒤집을 필요없다
            # 따라서 나온 횟수만큼 True False값을 계속 변환하면
            # 최종적으로 뒤집기를 시행해야 할지 말지를 정할 수 있다.
            rev = not rev

        if c == 'D':
            if not q:
                print("error")
                return
            
            if check_rev:
                q.pop()
            else:
                q.popleft()
    
    # 최종적으로 rev가 True라면
    # 뒤집기 시행
    if check_rev == True:
            q.reverse()
        
    print('[', end='')
    
    while q:
        num = q.popleft()
        
        if len(q) == 0:
            print(num, end='')
        else:
            print(num, end=',')
    
    print(']')
    return
    
# 테스트 케이스 개수
T = int(input())

for _ in range(T):
    cmd = input()

    # 명령이 앞에서부터 차례대로 적용되니까 편하게 deque 사용 (popleft())
    cmd = deque(cmd)
    n = int(input())
    arr = input()
        
    solution(cmd, n, arr)   

문제 해설

구현 자체는 크게 어렵지 않은 문제이나, reverse() 메소드를 반복적으로 사용할 시 시간 복잡도에서 성능 문제로 시간 초과가 발생한다.

나 역시 처음에 시간 초과를 당연하다는 듯이 마주했다..! 덱을 사용하면 list보다 훨씬 빠르게 작업을 수행할 것이라고 판단하여 정답이 될 줄 알았으나 reverse() 함수가 시간 차원의 성능이 좋지 못 하다는 것을 깨달았다.

문제에서 뒤집기 연산은 홀수번 시행하면 최종적으로 뒤집힌 배열이 반환되겠지만, 짝수번 시행하면 사실 하지 않은 것과 다름 없다. 따라서 ‘R’이 입력될 때 마다 매번 뒤집기 연산을 수행하지 않고,

check_rev = False

라는 boolean 변수를 따로 생성하여 이를 활용하여 ‘버리기’ 연산을 check_rev 변수의 값에 따라 앞, 또는 뒤에 맞춰서 배열의 정수를 제거하는 형식으로 문제를 풀었다.

밑은 문제 풀이 예시이다. (check_rev = False (default)일 때)