[백준] 5430. AC / python 파이썬

🚩 자료구조, 문자열, 파싱, 덱

 

thinking

0 ≤ p ≤ 100,000 , 0 ≤ n ≤ 100,000 이라 리터럴리 연산하면 시간초과 날거 같아서 규칙을 찾아봤다.

- R이 연속해서 홀수개면 뒤집고, 짝수개면 걍 그대로

- D는 연속한 개수만큼 삭제

=> R 홀짝 체킹할 flag변수 만들고, p연산 돌면서 앞에서부터 삭제할 개수랑 뒤에서부터 삭제할 개수 찾아서 삭제

 

코드

def sol(p, n):
    flag = 0  # 짝
    delete = [0, 0]
    # 홀이면 뒤집(뒷 숫자 삭제), 짝이면 stay(앞 숫자 삭제)
    for s in p:
        if s == 'R' and flag == 0:
            flag = 1
        elif s == 'R' and flag == 1:
            flag = 0
        elif s == 'D' and flag == 0:
            delete[0] += 1
        elif s == 'D' and flag == 1:
            delete[1] += 1
        if sum(delete) >= n:
            return 'error'

    # 삭제하고 뒤집
    res = num_lst[delete[0]:len(num_lst) - delete[1]]
    if flag:
        res.reverse()
    return "["+",".join(res)+"]"


T = int(input())
for tc in range(1, T+1):
    p = input()  # 수행할 연산
    n = int(input())  # 배열에 들어있는 숫자 개수
    num_lst = input().lstrip('[').rstrip(']').split(',')

    print(sol(p, n))

 

 

후기

백준 알고리즘 분류에 덱이라고 되어있어 덱이 뭔가 찾아봤더니 deque 였다 ㅎ;;;;

여태 디큐라고 하고 살았네;;^^;;

 deque 란 ?   양방향으로 넣고 뺄 수 있는 큐

(그림 출처:  https://ehclub.co.kr/1222 )

나는 덱으로 안풀었는데 덱으로 풀 수도 있다.