오늘 공부한 것은 스택/큐/데크다.
스택은 First In Last Out 방식이고 큐는 반대로 First In First Out 방식이다.
그리고 데크는 스택 + 큐의 개념이다.
- 양쪽에서 삭제와 삽입이 처리가 가능한 형태
- deque = doubled ended queue
Python의 경우, collections.deque 가 지원된다.
꼭 알아야 할 함수 - deque() , append() , appendleft() , pop() , popleft()
from collections import deque
deck = deque() # 신규 데크 생성 ([])
deck.append(1) # 오른쪽 끝에 1을 삽입 ([1])
deck.appendleft(2) # 왼쪽 끝에 2를 삽입 ([2, 1])
deck.append(3) # 오른쪽 끝에 3을 삽입 ([2, 1, 3])
a = deck.pop() # 오른쪽 끝에서 삭제 후 a에 그 값을 저장 ([2, 1])
print(a) # 3
b = deck.popleft() # 왼쪽 끝에서 삭제 후 b에 그 값을 저장 ([1])
print(b) # 2
이를 바탕으로 문제를 풀었다.
1번 문제 : 큐를 이용한 스택 구현 링크
def __init__(self):
self.deck=deque()
def push(self, x: int) -> None:
self.deck.append(x)
def pop(self) -> int:
return self.deck.pop()
def top(self) -> int:
return self.deck[-1]
def empty(self) -> bool:
return len(self.deck) == 0
2번 문제 : 스택을 이용한 큐 구현 링크
def __init__(self):
self.que = deque()
def push(self, x: int) -> None:
self.que.append(x)
def pop(self) -> int:
return self.que.popleft()
def peek(self) -> int:
return self.que[0]
def empty(self) -> bool:
return len(self.que) == 0
1번과 2번은 유사한 방식으로 풀었다. 다만 문제에서 2개의 큐와 2개의 스택을 사용할 것을 요구했는데 미처 그걸 생각하지 못하고 문제를 풀었다. 신기한건 그랬는데도 채점통과했다. 왜 통과했는지 2개를 이용한다는게 무엇인지 더 살펴봐야한다.
3번 문제(강주성) : 괄호 링크
def Parenthesis(s):
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack or stack[-1] != '(':
return "NO"
stack.pop()
else: #char != '(' and char !=')':
return "NO"
return "YES" if not stack else "NO"
n = int(input())
parentheses_list = [input() for _ in range(n)]
for parentheses in parentheses_list:
print(Parenthesis(parentheses))
for문에서 해당하는 char와 스택의 마지막 값을 이용해서 문제를 풀었다. 코칭을 받은 내용은 굳이 스택에 넣지 않고 count를 이용하면 더 심플해질것이라는 조언을 받았다.
4번 문제 : 프린터 큐 링크
def print_queue(n, m, lst):
que = deque(lst)
count = 0
while que:
current = que.popleft()
if any(current < doc for doc in que):
que.append(current)
else:
count += 1
if current == lst[m]:
return count
#틀렸습니다.
이렇게 if any를 이용해서 모든 크기 비교를 하면 될것이라고 생각했다. 또한 디버깅을 했을때도 제대로 값이 출력되어서 제출을 했는데 틀렸다고 나왔다. 그래서 매니저님께 도움을 구하니 current와 같은 값일때도 뒤로 넘어가는게 문제인것 같다는 대답을 들었다. 그래서 수정했다.
def print_queue(self, n, m, lst):
que = deque(lst)
count = 0
while que:
current = que.popleft()
m -= 1
if any(current < doc for doc in que):
que.append(current)
if m < 0:
m = len(que) - 1
else:
count += 1
if m == -1:
return count
여기서 포인트는 m값을 조절해주는것이다. 이러한 조치를 통해 m이 항상 유효한 인덱스를 유지하도록 하고, 리스트의 끝에 도달하면 처음으로 돌아가게 한다.
5번 문제 : 일일 온도 링크
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
answer = [0] * len(temperatures)
for i in range(len(temperatures)):
temp = temperatures[i]
while stack and temperatures[i] > temperatures[stack[-1]]:
index = stack.pop()
answer[index] = i - index
stack.append(i)
return answer처음엔 앞에서 부터 하나하나 비교하고 카운트 하는 방식으로 하려했는데 잘 안됐다. 그래서 어제한 투 포인터 알고리즘처럼 하면 어떨까했다. 위 코드는 결국 현재의 날씨와 스택에 쌓인 과거의 날씨를 비교해서 그 위치의 차이만큼을 계산하는 코드이다. 솔직히 100% 이해한것은 아니지만 대략적인 원리를 알았으니 반복하면 될것이라 생각한다.
*오늘 알게 된것
1. ==과 is의 차이
2. input().split()
3. [-1]은 배열의 마지막 값을 찾아준다.