[Coding test][골드V]BOJ #5430 (큐, 덱)

내 풀이

import sys
from collections import Counter, deque

test = int(sys.stdin.readline().rstrip())


for _ in range(test):

    #명령문 입력
    command = sys.stdin.readline().rstrip()

    #명령문 속 문자열 개수
    count = Counter(command)
    Rcount = count['R']
    Dcount = count['D']



    #데이터 개수 입력
    n = int(sys.stdin.readline().rstrip())
    data = sys.stdin.readline().rstrip()
    Q = deque()
    if n == 0:
        datalst = []

    else:
        #데이터입력
        data = data.replace('[', '')
        data = data.replace(']', '')
        datalst = list(map(int, data.split(',')))
        for i in datalst:
            Q.append(i)

    if Dcount > n:
            print('error')
            continue



    #명령어 실행
    Onpopleft = True

    for c in command:

        if c =='R':
            if Onpopleft == True:
                Onpopleft = False
            else:
                Onpopleft = True


        else:
            if c == 'D':
                if len(Q) == 0:
                    print('error')
                    break
                if Onpopleft:
                    Q.popleft()

                else:
                    Q.pop()

    if Rcount % 2 == 0:
        print("[{}]".format(",".join(list(map(str,Q)))))

    else:
        Q.reverse()
        print("[{}]".format(",".join(list(map(str,Q)))))

첫 골드 문제

실버로 꾸역꾸역 채워넣은 내 티어지만,,, 그래도 골드는 달았으니, 골드 문제는 풀어봐야하지 않겠는가?

그래서 백준 골드 티어 달성한 기념으로, 골드 문제를 풀어봤다.

이런ㅈ..

풀이

각 함수 R과 D에 대해서 데이터에 대한 연산을 실행한다.

R은 reverse(), D는 pop()을 통해 연산하는 것이 기본이다.

하지만 배열의 크기와 함수의 크기가 100,000이므로 함수 그대로 따라가면 무조건 시간초과가 난다. (O(N**2)의 시간복잡도)

연산을 단축시키는 방법을 생각해야하는데, 덱을 사용한다는 것이 먼저 떠올랐다. deque의 장점은 popleft()로 연산 시간을 단축할 수 있다는 것이다.

1. 리버스 2번은 원래 상태와 같다.
2. 리버스한 상태에서의 popleft()은 popleft()와 같다.

각 함수로 들어온 명령에 대해
R이 홀수 개 들어온 상황에서는 다음 D는 모두 pop()연산 이후 큐를 리버스한 것과 같다.
짝수 개 들어온 상황에서 다음 D는 popleft()연산을 실행한 것이다.

각 명령함수의 R이 들어오면 다음 연산을 popleft()할 것인가, 혹은 pop()을 할 것인가를
Onpopleft boolean값을 주어 on/off로 구현했다.

기초 상태는 True로 popleft()하도록, 그리고 R이 명령함수로 들어오면 false되며 pop()이 실행된다.

입출력 처리

이 문제의 진짜 핵심은 입출력 처리이다…. 질문만 봐도 입출력값에서 오류를 범하는 분들이 많았다.(나 포함…^^)

1. 데이터는 문자열로 [] 대괄호를 포함해 들어온다는것.(데이터 값 처리할때도 조심조심…)
2. 출력시 데이터는 deque를 리스트로 단순 변환하면 띄어쓰기가 포함되어 틀린 답이 된다는 것

이것과 문제의 기본조건을 숙지하면 바로 풀 수 있는 문제였다.