[백준 알고리즘] 5430번: AC ( Python / 파이썬 )

문제 설명

 

문제 접근

reverse(), delete()는 각 O(N)의 시간이 걸린다.

따라 70만 합 조건을 고려하여 계산했을 때 시간초과가 난다.

D가 첫 번째 수를 버리는 것이므로 deque의 pop(popleft)를 사용해 시간을 줄일 수 있다. 이는 평균적으로 O(1)의 시간이 걸린다.

R 또한 해결해야 하는데 두번 뒤집기(RR) = 처음과 똑같은 상태, 세번 뒤집기(RRR) = 한번 뒤집기(R) 라는 것을 이용한다.

뒤집은 횟수만 기억하였다가, 마지막에 홀수인지 짝수인지 판단만 하면 된다.

그러나 뒤집힌 상태에서 D가 수행되는 경우 이는 pop 또는 popleft (처음 부분 삭제 or 마지막 부분 삭제)로 나뉠 수 있다.

이를 R이 몇번째 등장하였는지 카운트하여 D가 수행되는 시점에서 뒤집힌 상태인지 고려하여 앞 또는 뒤를 삭제하는 알고리즘을 만들면 된다.

 

정답 코드

#5430번: AC

import sys
from collections import deque

t = int(sys.stdin.readline())
p = []

#테스트 반복
for _ in range(t):
    p = sys.stdin.readline() #ex: TDD
    n = int(sys.stdin.readline()) #배열에 들어있는 숫자 수
    a = sys.stdin.readline().rstrip()
    if a =='[]':
        q = deque()
    else:
        a = list(map(int, a.strip("[""]").split(",")))  # [1,2,3,4] 처리
        q = deque(a)

    #최소화된 p 만들기
    min_p = []
    r_count = 0
    for i in p:
        if i == 'R': r_count += 1
        elif i == 'D' and r_count % 2 == 0:
            min_p.append('D')
            r_count = 0
        elif i == 'D' and r_count % 2 == 1:
            min_p.append('R')
            min_p.append('D')
            r_count = 0
    if r_count % 2 == 1:
        min_p.append('R')

    # #최소화한 명령어 실행
    flag = False
    reverse_count = 0
    for i in p:
        if i == 'D':
            if len(q) < 1:
                print("error")
                flag = True
                break
            if reverse_count % 2 == 0:
                q.popleft()
            else: q.pop()
        else:
            reverse_count += 1

    if reverse_count % 2 == 1:
        q.reverse()

    if flag == False:
        print("[" + ",".join(map(str, q)) + "]")

 

---

 

5430번: AC