[큐를 이용한 스택 구현]
https://leetcode.com/problems/implement-queue-using-stacks/
스택을 이용해 다음 연산을 지원하는 큐를 구현하라
'''
# 내 답안
스택 구조를 만들기 위해 연결 리스트를 가져다 썼음
근데 굳이 필요했나 싶긴 함 그냥 리스트 가져다 pop 사용하면 되는 걸
'''
class Node:
def __init__(self, item, next):
self.item = item
self.next = next
class MyQueue:
def __init__(self):
self.last = None
def push(self, x: int) -> None:
if self.last:
node = self.last
while node.next:
node = node.next
node.next = Node(x, None)
else:
self.last = Node(x, self.last)
def pop(self) -> int:
result = None
if self.last:
result, self.last = self.last, self.last.next
return result.item
def peek(self) -> int:
return self.last.item
def empty(self) -> bool:
return self.last == None
'''
답안 1 스택 2개 사용
확실히 연결리스트 같은 구조를 필요하지 않는 경우에는 사용 안함
문제를 아마 잘못 판단한 느낌도 들지만, 일단 다른 예제를 좀더 봐야겠음
'''
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def push(self, x):
self.input.append(x)
def pop(self):
self.peek()
return self.output.pop()
def peek(self):
# output이 없으면 모두 재입력
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output[-1]
def empty(self):
return self.input == [] and self.output == []
'''
답안 2 리트코드
위에 답안과 비슷하게 스택을 2구조를 사용하지만,
답안 1에서는 peek 코드에서 진행되던 outStack 처리를 move라는 요소로 옮김
'''
class Queue(object):
def __init__(self):
self.inStack, self.outStack = [], []
def push(self, x):
self.inStack.append(x)
def pop(self):
self.move()
self.outStack.pop()
def peek(self):
self.move()
return self.outStack[-1]
def empty(self):
return (not self.inStack) and (not self.outStack)
def move(self):
if not self.outStack:
while self.inStack:
self.outStack.append(self.inStack.pop())[스택을 이용한 큐 구현]
https://leetcode.com/problems/implement-stack-using-queues/
큐를 이용해 다음 연산을 지원하는 스택을 구현하라
'''
개인 답안
일단 원체 파이썬 기능이 좋아서 그냥 바로 접근하든...뭘 하든 하면 될꺼 같은데
이렇게 쉬울리가 있나 하고 의심이 조금 됨
어쩌면 deque 같은거 말고 진짜 Queue를 사용해야할 듯 함
'''
def __init__(self):
self.queue = deque()
def push(self, x: int) -> None:
self.queue.append(x)
def pop(self) -> int:
temp = deque()
if self.queue:
while len(self.queue) > 1:
temp.append(self.queue.popleft())
last = self.queue.popleft()
self.queue = temp
return last
def top(self) -> int:
temp = self.queue.copy()
last = None
if self.queue:
while temp:
last = temp.popleft()
return last
def empty(self) -> bool:
if self.queue:
return False
else:
return True
'''
답안 1 push() 할 때 큐를 이용해 재정렬
코드가 정말 깔끔함
생각해보니 변수 따로 나누고 담고 헛짓거리 할바에 그냥 꺼내서 다시 추가하면 순서 회전초밥마냥 돌아가는데 그걸 몰랐네
처음 넣을때 순서를 다 정리해버리면, 가장 처음이 마지막 요소가 되버리면서
선입선출 방식으로 꺼내도 후입선출 방식으로 변경됨
'''
class MyStackAnswer:
def __init__(self):
self.q = collections.deque()
def push(self, x):
self.q.append(x)
# 요소 삽입 후 맨 앞에 두는 상태로 재정렬
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0[원형 큐 디자인]
https://leetcode.com/problems/design-circular-queue/
원형 큐 디자인
'''
개인 답안 1
Front():
start 대상
있냐 없냐: 있으면 가져와
없음: -1
Rear():
end 대상
있냐 없냐: 있으면 가져와
없음: -1
enQueue(value: int):
우리 앞에 Start 없지?:
다음거에 넣고 end + 1
return true
start 앞에 있는데요?:
그럼 못넣는 거지 뭐
return false
deQueue(): 원형 큐에서 요소를 삭제함, 성공시 true 반환
Start에 값 있냐:
있으면 빼
start + 1
end 너 나랑 같은데 있냐:
너도 같이가자 end + 1
return True
없는걸 어케 삭제해
return False
isEmpty(): 원형 큐가 비어있는지 확인
start랑 end랑 같이있냐
return 그럼 뭐 없는거지 뭐
둘이 별거중인데요
return 그럼 뭔일 있었나 보지
isFull(): 원형 큐가 차있는지 확인
# 큐 사이즈 가져와서-1, end-start한거랑 비교해봐 같으면 풀로 쓰고 있는거지
위에꺼 안되네, 우리 앞에 Start 있냐?:
있으면 다 쓴거지 뭐
# 1차 고민
자잘한 수정사항(크기 계산을 len에서 size 변수에 담음, 좀더 예쁘게 하려고)이 몇개 있었지만
현재 enQueue에서 막힘
만약 size가 5인 경우 배열은 0~4임
end 위치에서 +1를 하고 size로 나누면 4의 경우 5가 되어 5%5 = 0 으로 한바퀴 도는 절차를 계산하고,
+1을 하고 size만큼 나눈 나머지 값이 start랑 일치하면 공간이 꽉 차 있는걸로 생각하고 넣지 않는 루틴을 계산
다만 지금 계속 index out of range 오류가 남
end_position 변수가 문제인데
아예 초기 루틴부터 정리해야겠음
값을 1씩 넣는다고 가정할때 인덱스 변화
[None, None, None, None, None]
start: 0, end: 0
[1, None, None, None, None]
start: 0, end: 1
[1, 1, None, None, None]
start: 0, end: 2
[1, 1, 1, None, None]
start: 0, end: 3
[1, 1, 1, 1, None]
start: 0, end: 4
생각해보니 end 위치에 값은 늘 비어있음
end_position은 + 1 된 값이니 end에 바로 들어가고 이동해야함
또다른 문제는
현재 다음에 start 여부에 따라 값을 넣는 방식을 쓰려 했는데 계속 오류가 남
좀더 단순히 처리하는 방안으로 데이터 처리시 삭제하는 경우 None을 처리함
즉 None이면 공간이 존재한다는 뜻,
인덱스 계산에 문제를 해결하는 대신 None 판별로 변경
enQueue(value: int):
우리 앞에 자리 있지?:
다음거에 넣고 end + 1
return true
자리 없는뎁쇼?:
그럼 못넣는 거지 뭐
return false
자잘한 오류들이 되게 많았고
테스트 케이스가 갑자기 막 올라오는 단계에서 정신이 멍해짐
전부 작성하고 나니깐 코드가 너무 지저분해 보이긴 함
IF문을 비교할때 처리되는 경우를 먼저 쓰기 위해 if is not None인 경우를 먼저 썻지만,
생각해보닌 None인 경우 return을 빨리 시키고, else로 처리 구문을 넣으면 is not None에서 not 부분을 절약 가능함
'''
class MyCircularQueue:
def __init__(self, k: int):
self.start = 0
self.end = 0
self.queue = [None] * k
self.size = k
def enQueue(self, value: int) -> bool:
end_position = (self.end + 1) % self.size
if self.queue[self.end] is None:
self.queue[self.end] = value
self.end = end_position
return True
else:
return False
def deQueue(self) -> bool:
start_position = (self.start + 1) % self.size
if self.queue[self.start] is not None:
self.queue[self.start] = None
# 어차피 None이 아니면 end는 이미 앞으로 가있음 end 처리는 필요 없음
self.start = start_position
return True
else:
return False
def Front(self) -> int:
if self.queue[self.start] is not None:
return self.queue[self.start]
else:
return -1
def Rear(self) -> int:
if self.queue[self.end - 1] is not None:
# end는 추가 후 다음 위치로 이동, 마지막 데이터는 -1이 필요
return self.queue[(self.end - 1) % self.size]
else:
return -1
def isEmpty(self) -> bool:
if self.start == self.end and self.queue[self.start] is None:
return True
else:
return False
def isFull(self) -> bool:
# end가 None인 경우 값을 채우고 이동하기 때문에, start와 곂치면 Full인 상태
if self.end == self.start and self.queue[self.end] is not None:
return True
else:
return False
'''
답안 1
구조는 비슷하지만, 역시나 깔끔함
특히나 fron, rear 등에서 return을 한줄로 써내리고, if를 통해 바로 처리하는 부분은 배워야 겠음
추가로 Rear에서 -1 되면서 0을 넘어가는 경우를 고려하느라 최대값으로 나눈 나머지를 가져오는 코드가 있었는데
생각해보니 리스트는 -1하면 마지막 요소를 가져옴
괜히 넣었음
코드를 간결하고 예쁘게 쓰는 것도 알고리즘 능력에서 배워야 할 요소인 듯 함
실무에서는 적정수준에서 작성을 해야겠지만 그것도 잘 짤줄 알아야 하는 거니
미리 줄이는 법을 최대한 연습해야겠음
'''
class MyCircularQueueAnswer:
def __init__(self, k: int):
self.q = [None] * k
self.maxlen = k
self.p1 = 0
self.p2 = 0
# enQueue(): rear 포인터 이동
def enQueue(self, value: int) -> bool:
if self.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 + 1) % self.maxlen
return True
else:
return False
# deQueue(): front 포인터 이동
def deQueue(self) -> bool:
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) -> int:
return -1 if self.q[self.p1] is None else self.q[self.p1]
def Rear(self) -> int:
return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]
def isEmpty(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is not None
[카드2]
https://www.acmicpc.net/problem/2164
'''
개인 답안 1
반복 카드가 1장보다 많은 경우:
카드를 한장 드로우! 드로우한 카드를 무덤으로 보내고 내 턴을 마친다.
if 카드가 1개여?:
사쿠라네 사쿠라여
뭐하냐 while 손목 안찍고! break!
오레노 턴, 카드를 드로우 하고 list에 append한뒤 턴을 마친다.
아니 생각해보니깐 1개 남았는지 검증할 필요가 없네
1개 이상이면 2개씩 들어옴
1개는 나가리 되도 1개는 다시 append됨
어차피 append되면 1개 남으면 while 안돔 뭐한겨
'''
card_num = int(input())
card_list = deque(range(1, card_num+1))
while len(card_list) > 1:
card_list.popleft()
card_list.append(card_list.popleft())
print(card_list[0])[프린터 큐]
https://www.acmicpc.net/problem/1966
'''
개인 답안 1
일단 들어온 리스트에서 중요도에 따라서 계속 꺼내고 붙이고 반복하기로 함
자잘한 실수가 있었지만 그래도 잘 처리가 됨
어려울 줄 알았는데 의외로 쉬웠음 그냥 고민을 많이 한거 같음
'''
repeat = int(input())
for i in range(repeat):
count = 0
# 도큐맨트 개수를 받아오지만 사용은 안함
document_num, target = map(int, input().split())
import_list = deque(input().split())
# 리스트 내용이 존재시 계속 동작
while import_list:
# 현재 가장 앞에 있는 숫자가 최대 값에 비해 낮은지 분석
if import_list[0] < max(import_list):
# 낮은 경우 리스트의 마지막으로 옮김
import_list.append(import_list.popleft())
# 결과 대상인 target에 index도 당겨진 만큼 낮아짐
target -= 1
if target == -1:
# 만약 0번에 있던게 타겟이었으면 리스트 마지막에 갔음으로 index도 맞춰줌
target = len(import_list)-1
# 가장 앞에 있는 숫자가 최대 값인 경우 출력 진행
else:
# 출력된 문서들을 카운트함
count += 1
# 만약 출력된 것이 타겟인 경우 카운트를 출력하고 처리를 중지함
if target < 1:
print(count)
break
# 출력된 문서는 리스트에서 제외됨
import_list.popleft()
# 제외된 만큼 -1
target -= 1
'''
답안 1: 숏코딩
역시 숏코딩은 봐도 모르겠음
'''
import sys;r=lambda:map(int,sys.stdin.readline().split())
for _ in range(*r()):
n,m=r();p=[*r()];q=sorted(p);i=0;a=1
while 1:
if p[i]==q[-1]:
if i-m:a+=1;q.pop()
else:print(a);break
i=(i+1)%n
'''
답안 2: 인터넷
입력 받는 부분을 잘 축약하고,
로직이 좀더 깔끔한 느낌이 듬
앞으로 if문 안에 함수 호출은 줄여야겠음
max를 따로 뺴니 코드가 더 깔끔함
popleft를 따로 빼고 나중에 분기 처리를 하니 코드가 절약됨 이점은 배워야 겠음
'''
from collections import deque
import sys
t = int(input())
for i in range(t):
n, m = map(int, input().split())
queue = deque(list(map(int, sys.stdin.readline().split())))
count = 0
while queue:
best = max(queue) #현재의 최댓값이 가장 먼저 배출되므로 최댓값을 저장
front = queue.popleft() # 큐의 front를 뽑았으므로
m -= 1 # 내 위치가 한 칸 당겨진다.
if best == front: # 뽑은 숫자가 제일 큰 숫자일 때
count += 1 # 하나가 영원히 배출되므로 순번 하나 추가
if m < 0: # m이 0이라는 것은 뽑은 숫자가 내 숫자라는 뜻.
print(count)
break
else: # 뽑은 숫자가 제일 큰 숫자가 아니면
queue.append(front) # 제일 뒤로 밀려나게 됨
if m < 0 : # 제일 앞에서 뽑히면
m = len(queue) - 1 # 제일 뒤로 이동
아 속이 안좋음
건강도 신경써야하는데, 따로 운동 시간을 또 배정이 필요하고
식단도 따로 건강식으로 변경해야겠음
썩을놈의 김치랑 발효되고 있는 간장 메추리알 빨리 쳐먹고 뒤져야지
달콤살벌