#13 큐(Queue) 활용

 큐(Queue)는 마지막에 삽입한 데이터가 가장 먼저 제거되는 스택과는 달리 먼저 삽입된 데이터가 먼저 제거되는 선입선출(FIFO)식 자료구조이다.  이름 그대로 대기열의 구현에 사용되며 네트워크상에서 패킷의 전송이나 OS의 스케줄링 등에서도 큐가 사용된다.  큐가 사용되는 대표적인 문제는 BFS 문제이며 그 외에도 큐의 성질을 활용해야하는 문제나 큐의 변형 자료구조인 데크(Deque)나 우선순위 큐(Priority Queue) 등을 활용한 문제들도 있다.  이번에는  큐와 데크를 활용하여 해결할 수 있는 문제 두 가지를 알아본다.

 

 

1. 프린터 큐 (https://www.acmicpc.net/problem/1966)

 문서마다 중요도가 주어지고 큐에서 가장우선도가 높은 문서들은 모두 큐의 맨 뒤로 보내며 처음으로 만난 최고 우선도의 문서를 제거하여 출력하는 프린터 큐를 구현하는 문제.  중요도가 중복되지 않는다면 정렬로 끝날 간단한 문제지만 같은 우선도를 가진 문서가 존재할 수 있기 때문에 큐를 활용하여 해결해야한다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol1966():
    res = []
    # 테스트케이스 루프
    for _ in range(int(input())):
        n, m = map(int, input().split())
        
        # 문서의 중요도와 초기 인덱스를 묶어서 리스트형태로 저장
        docs = list(zip(map(int, input().split()), range(n)))
        
        # 프린트 시작
        for i in range(1, n+1):
        	# 가장 우선도가 높은 문서중 가장 앞에 있는 문서를 출력
            # 문서의 초기인덱스가 m과 같다면 res에 답을 append하고 다음 테스트케이스로
            p = max(docs, key=lambda x:x[0])
            if p[1] == m:
                res.append(i)
                break
               
            # 실제로는 출력할 문서가 나올때까지 모든 문서를 하나하나 큐의 맨 뒤로 보내야하지만
            # 빠르고 간결하게 처리하기 위해 리스트 슬라이싱을 사용하여 같은 결과를 낸다.
            # 출력할 문서를 기준으로 좌우를 슬라이싱한뒤 순서를 바꾸어 이어붙인다.
            pi = docs.index(p)
            docs = docs[pi+1:] + docs[:pi]
            
    return '\n'.join(map(str, res))


if __name__ == '__main__':
    print(sol1966())

 

 

2. AC (https://www.acmicpc.net/problem/5430)

 R은 배열을 뒤집는 연산, D는 배열의 첫 번째 숫자를 버리는 연산이라고 정의할 때, 초기 배열과 연산순서가 주어지면 모든 연산을 수행한 뒤 배열의 상태를 출력하는 문제.  배열을 실제로 뒤집는 방식으로는 당연하게도 시간초과가 발생한다.  배열을 뒤집는다는 것이 곧 D 연산으로 버릴 숫자의 위치가 첫 번째와 마지막 사이에서 바뀌는 것이란걸 알면 양방향 큐인 데크를 활용하여 간단하게 해결 가능하다.  이를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol5430():
    res = []
    for t in range(int(input())):
        cmd = input().rstrip()
        n = int(input())
        
        # D 연산의 횟수
        d = cmd.count('D')
        
        seq = input()
        
        # D 연산의 횟수가 수열의 크기보다 크면 에러
        if d > n:
            res.append('error')
        # 같다면 빈 배열
        elif d == n:
            res.append('[]')
            
        else:
            seq = list(seq[1:-2].split(','))
            # 두번 연속 뒤집기는 의미가 없음
            cmd = cmd.replace('RR', '')

            # 앞에 나온 R의 횟수가 짝수면 앞에서 버리기, 홀수면 뒤에서 버리기
            cmd = list(map(len, cmd.split('R')))
            seq = seq[sum(cmd[0::2]):n - sum(cmd[1::2])]
            if len(cmd) % 2 == 0:
                seq.reverse()
            res.append('[' + ','.join(seq) + ']')
    return '\n'.join(res)


if __name__ == '__main__':
    print(sol5430())

무의미한 뒤집기 연산을 제거하고 D연산의 횟수와 수열의 크기만으로 해결 가능한 케이스를 빠르게 처리하여 남는 것들만 실제로 연산들을 수행한다.  연속뒤집기를 제거하고나서 split('R')을 해주면 짝수번째 명령의 길이는 앞에서 버리는 D연산의 횟수, 홀수번째 명령의 길이는 뒤에서 버리는 D연산의 횟수가 된다. 이를 이용하면 일일히 뒤집기와 pop을 실행할 필요도없다.  실제로 데크를 사용하더라도 시간초과는 발생하지 않지만 이 방법을 사용하면 시간을 많이 단축할 수 있다.  물론 동작 원리는 결국 데크를 사용하는 것과 동일하다.