[백준] 5430 AC (파이썬 python)

 

 

문제 링크

 

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

5430번: AC

 

 

문제 풀이

 

 

입력이 [1, 2, 3]의 형태로 들어오기 때문에, 이를 파싱해서 deque에 넣어 사용했습니다.

nums = deque(input().rstrip()[1:-1].split(','))

 

 

단순한 구현으로 풀면 풀리는 문제이지만, 정답률이 낮은 이유는 시간 초과에 있었습니다.

본 문제는 시간제한이 1초입니다. 파이썬에서는 1초에 약 2000만번의 연산이 가능합니다.

pop 연산은 O(1)의 시간복잡도이므로 큰 문제가 없지만, reverse 연산의 경우 O(n)의 시간복잡도를 가지기 때문에

테케 개수, 수의 길이, reverse 연산의 수에 따라 2000만번을 훨씬 넘을 수도 있는 것입니다.

 

reverse 연산을 최소화하기 위해, reverse 연산 정보를 저장해둔 뒤 마지막에 한 번만 할 수 있도록 구현했습니다.

rev = 0
if rev % 2 == 1:
    nums.reverse()
return "[" + ",".join(nums) + "]"

 

또한, D 연산에 대해서는 rev의 홀수 여부에 따라 홀수일 경우 reverse된 상태이므로

맨 앞이 아닌 뒤에서 pop할 수 있도록 구현했습니다.

 

전체 코드

from collections import deque

def execute(cmds, nums):
    rev = 0
    for cmd in cmds:
        if cmd == 'D':
            if not len(nums):
                return 'error'
            if rev % 2 == 0:
                nums.popleft()
            else:
                nums.pop()
        else:
            rev += 1
    if rev % 2 == 1:
        nums.reverse()
    return "[" + ",".join(nums) + "]"

t = int(input())
for _ in range(t):
    cmds = input().rstrip()
    n = int(input())
    nums = deque(input().rstrip()[1:-1].split(','))
    if n == 0:
        nums = deque()
    print(execute(cmds, nums))