[백준 BOJ] 5430 번: AC -python

SUN·2022년 8월 3일

algorithm

목록 보기

13/30

이번에 풀어볼 문제는 AC이다.

문제

풀이 과정

이 문제를 보고 처음 든 생각은 덱을 써야겠다였다.
왜냐면 R함수를 적용했을 때 리스트를 진짜 뒤집지 않고
pop 하는 방향만 반대 쪽으로 바꿔주면 되겠다는 생각이 들었기 때문이다.
그러면 양방향으로 pop을 할 수 있으면 되겠고,
이걸 가능하게 하는 게 덱이기 때문에 덱을 써야겠다 싶었다.

예를 들어서
[1,2,3,4] 에
원래는 RDD 연산을 한다고 하면

R -> [4,3,2,1] 로 뒤집고
D-> [2,1,3]
D -> [2,1]
이렇게 앞에서 두개를 pop해야 한다.
하지만 아래처럼 생각할 수도 있다.

reversed = False로 초기화 해둔 다음에

R-> [1,2,3,4] reversed = !reversed
이렇게 리스트는 그대로 두고 pop할 방향만 반대로 설정해두고

D -> [1,2,3]
D -> [1,2]

이렇게 모든 연산을 끝내고
최종 방향이 뒤집힌 방향이면 뒤집어주고 아니면 그대로 출력한다.
즉, reversed가 True면 뒤집고 False면 그대로 출력하도록 하면된다.
이 경우에는 뒤집힌 방향(reversed=True)이니까 뒤집은 다음에 출력한다.

이 방법을 사용하면 전자의 결과와 똑같지만 더 효율적으로 문제를 해결할 수 있다.

최종 코드

from collections import deque

T = int(input())

for i in range(T):
    try:
        p = input()  # 연산들
        n = int(input())  # 리스트 개수
        lst = input().strip("[]")  # 리스트

        dq = deque()

        if lst != "":
            dq.extend(lst.split(","))

        # 연산 방향 (리스트가 뒤집어졌는 지 여부)
        # False면 앞에서 부터, True면 뒤에서 부터 pop
        reversed = False
        for command in p:
            if command == "R":  # 뒤집으라는 명령이면 연산을 먹일 방향을 반대로
                reversed = not reversed

            else:
                if reversed:  # 뒤집어져있으면
                    dq.pop()  # 뒤에서 부터 pop
                else:  # 아니면
                    dq.popleft()  # 앞에서 부터 pop

        if reversed:  # 최종적으로 뒤집어진 방향이면
            dq.reverse()  # 한번 뒤집어줌

        print("[" + ",".join((dq)) + "]")
    except:
        print("error")