백준 5430: AC (파이썬)

문제 : https://www.acmicpc.net/problem/5430

5430번: AC

---

코드

#https://teching.tistory.com/
from collections import deque
import sys

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    ops = sys.stdin.readline().rstrip()
    sys.stdin.readline()
    # 큐 변환
    nums = sys.stdin.readline()[1:-2]
    reverse = -1
    if nums == '':
        que = deque()
    else:
        que = deque(nums.split(','))
    # 명령어 처리
    for op in ops:
        if op == 'R':
            reverse *= -1
        elif op == 'D':
            if que:
                if reverse == 1:
                    que.pop()
                else:
                    que.popleft()
            else:
                print('error')
                break
    # 출력
    else:
        if reverse == 1:
            que.reverse()
        print("[" + ",".join(que) + "]")

해설

해당 문제는 R이 나올 때마다 큐를 뒤집어주면 시간 초과가 발생하기 때문에 뒤집지 않고 처리하는 방법을 생각해내는 것이 포인트인 문제였다.

나는 이부분을 que.reverse()를 하지 않고 reverse여부를 저장하는 변수를 두어서 처리하였다.

뒤집힌 상태이면 배열의 마지막 수를 버리고 뒤집혀있지 않으면 배열의 첫 번째 수를 버린다.

이것만 생각하면 파이썬이 제공하는 기능으로 쉽게 풀리는 문제이다.

 

collection.deque

일반적인 큐와 비슷하지만 입구와 출구가 2개인 양방향 큐.

일반적인 리스트가 pop(0)으로 첫 번째 요소를 꺼낼 때 O(n)인 반면 deque는 popleft()로 O(1)이다.

따라서 pop(0)을 써야하는 문제일 경우 deque를 통해서 풀면 좋다.

사용방법

 

import collections
from collections import deque

두 방법중 편한 것을 사용하면 된다.

deque에서 사용 가능한 메서드(list에서 사용 가능한 메서드들 또한 사용 가능하다.)

deque가 데크를 저장한 변수 명일 때

• deque.append(item): 데크의 오른쪽 끝에 item 추가
• deque.appendleft(item): 데크의 왼쪽 끝에 item 추가
• deque.pop(): 데크의 오른쪽 끝 요소를 꺼낸다.
• deque.popleft(): 데크의 왼쪽 끝 요소를 꺼낸다.
• deque.extend(array): 데크의 오른쪽에 array(배열)을 합친다.
• deque.extendleft(array): 데크의 왼쪽에 array(배열)을 합친다.
• deque.rotate(num): 데크를 num만큼 회전한다.(양수: 오른쪽, 음수: 왼쪽)

해당 메서드들을 사용 가능하다.