[백준/Python] 5430: AC

[백준/Python] 5430: AC

정답률이 19%인것부터 예상하긴 했지만 열심히 코드를 써서 내보니 시간초과가 났다...

• 처음 제출했던 코드

import sys
from collections import deque

t = int(sys.stdin.readline())

for i in range(t):
    command = list(sys.stdin.readline().strip("\n"))
    n = int(sys.stdin.readline())
    line = sys.stdin.readline().strip("[""]\n")
    check = True
    try:
        arr = deque(map(int, line.split(",")))
    except:
        arr.clear()
    for j in command:
        # R : 배열의 순서를 뒤집는다.
        if j == "R":
            arr.reverse()
        # D : 첫번째 수를 버린다.(배열이 비어있는 경우 error 출력)
        elif j == "D":
            if len(arr) == 0:
                print("error")
                check = False
            else:
                arr.popleft()
    if check == True:
        print(str(arr).strip("deque("")"))

찾아보니 reverse()함수의 시간복잡도가 $O(n)$이라 실행시간에 큰 영향을 주고 있었다.
조금만 생각해 보니 R이 등장할 때마다 뒤집는 것은 비효율적이라는 생각이 들었다. R이 짝수번 등장한다면 애초에 뒤집을 필요가 없고 홀수번 등장한다고 하더라도 마지막에 한번만 뒤집어 주면 된다.

그런데 D가 등장한다면 큐를 뒤집고 뒤집지 않고에 따라 연산 결과가 달라지게 된다.
이 문제를 해결하는 방법은 의외로 간단한데, 우선 커맨드에서 R이 등장한 개수를 계속 카운트한다. 그리고 D가 등장했을 때, R의 등장 횟수에 따라 그 시점에 홀수번 등장했으면 popleft()하고, 짝수번 등장했으면 pop()한다.

if j == "R":
    cnt += 1
    # D : 첫번째 수를 버린다.(배열이 비어있는 경우 error 출력)
elif j == "D":
    if len(arr) == 0:
        print("error")
        check = False
        break
else:
    if cnt%2 != 0:
        arr.pop()
    else:
        arr.popleft()

이후 큐를 출력할 때 R이 홀수번 등장했으면 배열을 뒤집어 출력해주고, 그렇지 않다면 그대로 출력하면 된다.

if cnt%2 != 0 and len(arr) != 0:
	arr.reverse()
print(str(arr).strip("deque("")").replace(" ", ""))

소스코드

---

import sys
from collections import deque

t = int(sys.stdin.readline())

for i in range(t):
    command = list(sys.stdin.readline().strip("\n"))
    n = int(sys.stdin.readline())
    line = sys.stdin.readline().strip("[""]\n")
    check = True
    try:
        arr = deque(map(int, line.split(",")))
    except:
        arr = deque()
    cnt = 0
    for j in command:
        # R : 배열의 순서를 뒤집는다.
        # 실행시간을 최적화하기 위해 r의 개수를 센 후 
        # 홀수개이면 D 연산에서 pop하고 짝수개이면 popleft한다.
        # 마지막에는 총 cnt수에 따라 홀수개이면 뒤집고 짝수개이면 뒤집지 않는다
        if j == "R":
            cnt += 1
        # D : 첫번째 수를 버린다.(배열이 비어있는 경우 error 출력)
        elif j == "D":
            if len(arr) == 0:
                print("error")
                check = False
                break
            else:
                if cnt%2 != 0:
                    arr.pop()
                else:
                    arr.popleft()
    if check == True:
        if cnt%2 != 0 and len(arr) != 0:
            arr.reverse()
        print(str(arr).strip("deque("")").replace(" ", ""))

시행착오를 많이 해서 코드가 좀 복잡하게 짜여졌다. (한시간 반정도 트라이한듯..) 출력 형식에도 신경써야 하고 런타임 에러도 계속 난다. reverse() 함수의 실행시간을 최소화하는 것이 가장 주의해야 할 부분처럼 보였지만 이것보다 런타임 에러 고치는데에 더 많은 시간을 썼다. 그래도 재미있는 문제였다.