큐를 이용한 스택 구현 https://leetcode.com/problems/implement-stack-using-queues
Implement Stack using Queues - LeetCode
Can you solve this real interview question? Implement Stack using Queues - Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the
leetcode.com
문제 접근
- 왼쪽으로 추가하고, 왼쪽으로 삭제
- 파이썬에서 메소드를 지원해서 바로 해결 하였다.
아쉬운, 놓쳤던 부분
- 스택과 큐에 대해 아직 응용 할 수 없다고 많이 느끼고있다.
맞은 결과
class MyStack:
def __init__(self):
self.stack = collections.deque()
def push(self, x: int) -> None:
self.stack.appendleft(x)
def pop(self) -> int:
return self.stack.popleft()
def top(self) -> int:
return self.stack[0]
def empty(self) -> bool:
return len(self.stack) == 0
맞은 결과 - 파이썬 알고리즘 인터뷰
class MyStack:
def __init__(self):
self.stack = collections.deque()
def push(self, x: int) -> None:
self.stack.append(x)
for i in range(len(self.stack) - 1):
self.stack.append(self.stack.popleft())
# 2 1 3
# 1 3 2
# 3 2 1
def pop(self) -> int:
return self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def empty(self) -> bool:
return len(self.stack) == 0
스택을 이용한 큐 구현 https://leetcode.com/problems/implement-queue-using-stacks
Implement Queue using Stacks - LeetCode
Can you solve this real interview question? Implement Queue using Stacks - Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement t
leetcode.com
문제 접근
- 스택 2개를 이용해서 큐를 만들어라고 했다.
- 생각이 안나서 책의 내용을 확인 하고 이해하고 짰다.
- input, ouput 스택을 2개가 있으면
- input = [1,2,3]에서 pop을 하면 3부터 나오니 이걸 이용하여 output에 넣어준다.
- output = [3,2,1]로 들어가니 1로 정상적으로 큐 형식으로 된다.
- peek에서 output에 값을 넣어주는 과정을 하고 pop을 한다.
아쉬운, 놓쳤던 부분
- 두번째 코드에서 push를 할 때 반복문으로 정렬을 할려고 했지만 안돼서 책의 해답을 확인 하였다. 전부 다 지우면서 popleft의 값을 append 하는게 맞았다.
맞은 결과 - 파이썬 알고리즘 인터뷰
class MyQueue:
# input에 차례대로 1,2,3
# output에 다시 3,2,1을 넣어주고
# output을 꺼낸다.
def __init__(self):
self.input = []
self.output = []
def push(self, x: int) -> None:
self.input.append(x)
def pop(self) -> int:
self.peek()
return self.output.pop()
def peek(self) -> int:
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output[-1]
def empty(self) -> bool:
return len(self.input) == 0 and len(self.output) == 0
원형 큐 디자인 https://leetcode.com/problems/design-circular-queue
Design Circular Queue - LeetCode
Can you solve this real interview question? Design Circular Queue - Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the
leetcode.com
문제 접근
- 원형 큐로 만들어야하니 포인터 2개 만들어서 진행을 할려고 했다. front쪽 포인터가 움직여야 하는걸 인지를 못했다. 그래서 당연히 테스트케이스만 통과를 하고 제출은 실패했다
아쉬운, 놓쳤던 부분
- 원형 큐를 제대로 이해하지 못하고 무작정 작성을 한게 문제였던것 같다.
- 이해하고 끝까지 가면 시간을 너무 잡아먹기 때문에 일단 해답을 보는식으로 하는 방향으로 가긴 가야한다.
틀린 결과
class MyCircularQueue:
def __init__(self, k: int):
self.queue = collections.deque()
self.front = 0
self.rear = 0
self.size = k
def enQueue(self, value: int) -> bool:
if self.rear < self.size:
self.rear += 1
self.queue.appendleft(value)
return True
return False
def deQueue(self) -> bool:
if len(self.queue) != 0:
self.rear -= 1
self.queue.popleft()
return True
return False
def Front(self) -> int:
return self.queue[0]
def Rear(self) -> int:
return self.queue[0]
def isEmpty(self) -> bool:
return len(self.queue) == 0
def isFull(self) -> bool:
return self.rear == self.size
해답 확인 후 분석
책을 읽고 원형 큐의 원리를 파악을 먼저 하였다. front, rear는 별개로 보는 느낌으로 진행
rear 값을 호출 할 때 왜 -1을 해주지 ?
- front, rear는 같은 위치
- 추가 시 rear는 한칸 앞으로
- 그렇기에 rear의 값을 가져올땐 -1을 해줘야함
왜 삽입, 삭제 할때 % 연산자가 사용 됐지 ?
- 나머지값이 그 다음 인덱스로 떨어지고
- 최대값이 되면 0으로 초기화
책에서는 공백 한칸으로 무조건 남겨두는데 어떻게 == 사용하지 ?
- 값을 끝까지 채웠을때는 모든 공간을 사용한다.
- 그래서 front,rear의 위치가 같다.
맞은 결과 - 파이썬 알고리즘 인터뷰
class MyCircularQueue:
def __init__(self, k: int):
self.queue = [None] * k
self.front = 0
self.rear = 0
self.size = k
def enQueue(self, value: int) -> bool:
if self.queue[self.rear] is None:
self.queue[self.rear] = value
self.rear = (self.rear + 1) % self.size
return True
else:
return False
def deQueue(self) -> bool:
if self.queue[self.front] is None:
return False
else:
self.queue[self.front] = None
self.front = (self.front + 1) % self.size
return True
def Front(self) -> int:
return -1 if self.queue[self.front] is None else self.queue[self.front]
def Rear(self) -> int:
return -1 if self.queue[self.rear-1] is None else self.queue[self.rear-1]
def isEmpty(self) -> bool:
return self.front == self.rear and self.queue[self.front] is None
def isFull(self) -> bool:
return self.front == self.rear and self.queue[self.front] is not None
카드2 https://www.acmicpc.net/problem/2164
2164번: 카드2
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가
www.acmicpc.net
문제 접근
- 1234를 0번째를 없애는것
- 2를 맨 뒤에 보낼 것
- 반복
- 마지막에 남은 값
맞은 결과
import collections
N = input()
queue = collections.deque(i+1 for i in range(int(N)))
while len(queue) > 1:
queue.popleft()
queue.append(queue.popleft())
print(int(queue[0]))
프린터 큐 https://www.acmicpc.net/problem/1966
1966번: 프린터 큐
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에
www.acmicpc.net
문제 접근
- 문제는 이해를 했는데 입력, 출력 부분은 아무리 읽어도 이해가 안갔다. 다음에는 좀 더 꼼꼼히 읽어봐야겠다.
아쉬운, 놓쳤던 부분
- 결국 해답을 보면서 문제를 봤는데, 이해가 너무 안가서 전체적으로 문제가 많다 해답을 보면서 파이썬 문법을 아직 이해 못한게 많다고 느꼈다.
해답 확인 후 분석
이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다.
- i, rank = dq.popleft()
- if rank == index[-1] 아닐 경우
- dq.append((i, rank))
정렬된 index와 dq를 비교를 하는 원인이 뭘까?
- dq = [(0,1)]
- if rank == index[-1]:
맞은 결과 - 출처(벨로그)
from collections import deque
test_case = 1 # 찾을려는 문서 총 개수
for _ in range(test_case):
dq = deque()
n, m = map(int, "6 0".split()) # 문서 개수, 찾을려는 위치
index = list(map(int, "1 1 9 1 1 1".split())) # 문서
for i, rank in enumerate(index): # index, value 반복
dq.append((i, rank)) # dq에 [index, value] 추가
index.sort() # 정렬
count = 0
while dq:
i, rank = dq.popleft() # i에 인덱스, rank에 중요도를 담는다.
# dq에서 꺼낸 첫번째 값과 index의 마지막 값이 같은지
if rank == index[-1]:
index.pop()
count += 1
# 인덱스와 찾을려는 인덱스가 같으면 끝
if i == m:
print(count)
break
else:
dq.append((i, rank))
'항해99' 카테고리의 다른 글
항해99 알고리즘 6회차 (0) | 2023.12.19 |
---|---|
항해99 알고리즘 5회차 (2) | 2023.12.15 |
항해99 알고리즘 3회차 (0) | 2023.12.13 |
항해99 알고리즘 2회차 (0) | 2023.12.12 |
항해99 알고리즘 1회차 (2) | 2023.12.11 |