[Python] 큐 유형문제(백준)

1. 11866번 ( 큐 응용 )

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

import sys
from collections import deque
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())    
    que= deque()

    for i in range(1,N+1):
        que.append(i)

    print('<',end="")
    
    while(len(que)!=1):
        for cnt in range(1,K):
            que.append(que.popleft())
        
        print(que.popleft(), end=", ")
        

    print(que.popleft(),end="")

    print('>',end="")
    

if __name__=="__main__":
    main()

 

 

 

2. 24511번 ( 큐 & 스택 응용 )

https://www.acmicpc.net/problem/24511

24511번: queuestack

 

2-1. 알고리즘 동작 과정

2-1-1. 특징 (주의사항)

: 이중 for문을 이용해서 계속 시간초과가 발생하였다

import sys
from collections import deque

input = sys.stdin.readline

def Pop(struct,arr,idx):
    if(struct[idx]==1):
        return arr[idx].pop()
    else:
        return arr[idx].popleft()
    
    

def main():
    N = int(input())
    struct = list(map(int,input().split()))
    element = list(map(int, input().split()))
    M = int(input())
    item = list(map(int,input().split()))

    #스택, 큐를 원소로 하는 리스트
    arr=[]
    for i in range(N):
        arr.append(deque())
    
    #초기원소 삽입
    for i in range(N):
        arr[i].append(element[i])

    #최종 pop원소 저장
    res=[]
    
    for i in range(M):
        arr[0].append(item[i])
        for j in range(N-1):
            popdata=Pop(struct, arr, j)
            
            j+=1
            arr[j].append(popdata)
        
        last = N-1
        res.append(Pop(struct, arr, j))


    for i in res:
        print(i, end =" ")

        


if __name__=="__main__":
    main()

 

2-1-2. 알고리즘 동작 분석

: 그림을 보면 스택에 삽입하거나 pop할 때는 스택의 구조에 변화가 없다

: 기존 스택에 있던 원소는 사용할 일이 없음!

: 큐 하나만 이용

 

                  ↓ 아래와 같이 생각할 수 있음

 

 

→ 기존 원소는 큐에 appendleft()

→ 새로 추가하는 원소는 큐에 append()

→ 원소를 꺼낼때는 popleft()

 

 

 

 

 

 

2-2. 최종 구현

import sys
from collections import deque

input = sys.stdin.readline


def main():
    N = int(input())
    struct = list(map(int,input().split()))
    element = list(map(int, input().split()))
    M = int(input())
    item = list(map(int,input().split()))

    queue= deque()
    
    for i in range(len(element)):
        if(struct[i]==0):
            queue.appendleft(element[i])

    for i in range(M):
        queue.append(item[i])
        print(queue.popleft(), end=" ")

        


if __name__=="__main__":
    main()