복습하기4
큐를 이용한 스택구현, 스택을 이용한 큐 구현, 원형 큐 디자인, 프린터 큐, 카드2
03/15/2022
큐 → FIFO
#큐를 풀땐 그냥 단순히 deque를 사용해야한다고 생각하라고 했다.
class Node:
def __init__(self, item, next):
self.item = item
self.next = next
class Queue:
def __init__(self):
self.front = None #시작할때 프론트녀석을 만들어주는것이 굉장히 중요하다.
def is_empty(self): #비었는지 안비었는지 보려면
return self.front is None #none이면 빈것이고 아니면 안빈것
def push (self, value): #무언가를 넣어줄땐
if not self.front: #만약에 이녀석이 비었다면, 새로만든 벨류를 넣어주자.
self.front = Node(value, None)
return
node = self.front #안비었다면,
while node.next: #계속 끝까지간다.
node = node.next #다음이 존재하는한 끝까지간다
node.next = Node(value, None) #while문이 끝났을땐 끝까지 도달한상태이다.
#새로만든 노드로 마무리한다.
def pop(self):#꺼낼땐
if not self.front: #프론트가 없으면 아무것도 안준다.
return None
node = self.front #비지않았다면 제일앞에녀석을꺼낸다
self.front = self.front.next #기존녀석에 다음녀석을 새로운 프론트로 지정해준 후에
return node.item #제일앞에녀석꺼내서 노드의 아이템 즉 데이터를 반환하면된다.카드2
https://www.acmicpc.net/problem/2164
from collections import deque
def test_problem_queue(num):
deq = deque([i for i in range(1, num + 1)]) #1-num까지 데큐화된다
while len(deq) > 1: #하나가 남을때까지 밑에 두과정 한다.
deq.popleft() #앞에있는거버려
deq.append(deq.popleft()) #그리고 그 다음 위에오는 녀석은 다시 아래로 붙여.
return deq.popleft()
#deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
큐를 이용한 스택구현
import collections
class MyStack:
def __init__(self):
self.front = collections.deque()
def push(self, val):
self.front.append(val)
for i in range(len(self.front) - 1):
self.front.append(self.front.popleft())
def pop(self):
return self.front.popleft()
def top(self):
return self.front[0]
def empty(self):
return len(self.front) == 0
#deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.스택을 이용한 큐구현
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def empty(self):
return self.output and self.input is None
def push(self, x):
self.input.append(x)
#왜이리도 어렵게 구현하는건지참... 난 peek부분없이구현함..
def pop(self):
self.peek()
return self.output.pop()
def peek(self):
if not self.output:
while self.input:
self.output.append(self.input.pop())
def empty(self):
return self.input == [] and self.output == []원형 큐 디자인
지금까지 배운 선형 큐와 스택들을 보완한 것을 원형큐로 만든것이다.
class MyCircularQueue:
def __init__(self, k):
self.q = [None] * k
self.maxlen = k # k: 최대길이
self.p1 = 0 # front
self.p2 = 0 #rear
def enQueue(self, value): #rear 포인터 이동
if self.q[self.p2] is None: # rear가 비어있으면~
self.q[self.p2] = value #끝에 데이터 넣어주고
self.p2 = (self.p2 + 1) % self.maxlen #한칸 앞으로 가는데 최대길이(maxlen) 안넘도록 한다
return True
else:
return False #끝에 뭐 있으면 말고~
def deQueue(self): #front 포인터 이동
if self.q[self.p1] is None:
return False
else:
self.q[self.p1] = None #프론트 비워주고
self.p1 = (self.p1 + 1) % self.maxlen #한칸 앞으로 이동한후에 최대길이 지켜준다
return True
def front(self):
return -1 if self.q[self.p1] is None else self.q[self.p1] #만약 아무것도 없으면 -1 이상한 놈이니까
#만약에 프론트 아무것도 없으면,, 그리고 뭔가있다? 그값 보여준다.
def Rear(self):
return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1] # 만약 아무것도 없으면 -1 이상한 놈이니까
def isEmpty(self):
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self):
return self.p1 == self.p2 and self.q[self.p1] is not None프린터 큐
큐와 데크를 이용하여 푸는 문제...
카운터를 하나 만들어서 풀기...아 백준은 문제이해부터 어려워..
from typing import List
import collections
from sys import stdin
class Solution:
def printerQueue(self, docCount: int, docIndex: int, priority: List[int]) -> int:
printer = collections.deque()
for i, p in enumerate(priority):
printer.append([i, p])
answer = 0
while printer:
i, p = printer.popleft()
if p == max(priority):
answer += 1
if i == docIndex:
return answer
else:
priority.remove(p)
else:
printer.append([i, p])
for i in range(int(stdin.readline())):
N, M = map(int, stdin.readline().split())
priority = list(map(int, stdin.readline().split()))
print(Solution().printerQueue(N, M, priority))