Queue and practice questions
Queue
Declare deque
We can declare queue with no initial data, or with a starting position.
queue = deque()
queue = deque([start_index, end_index])
queue = deque(some_list)
.peek() = deque[0]
We peek queue’s front-most element via deque[0]. Btw for stack it is [-1].
popleft()
If using it as a queue, popleft() removes the front-most element. For stack, it is just pop()
append((whatever elements in a list))
Unlike list, deque’s append is different. In list, we do .append([list of elements]) but in deque, we don’t use the square brackets but instead use circular brackets. If you are adding a tuple like (dx,dy) and an int like cost to deque, we do
deque.append(((x,y),cost))
!queue.isEmpty() = while(queue)
I kept on using while stack or while queue without knowing what it really meant but the while loop goes on as long as there is something in the queue or stack.
Practice questions
기능개발
https://school.programmers.co.kr/learn/courses/30/lessons/42586
I tried calculating the day of each progress and if current day is less than the recorded previous day(count), then we just increment hola, which I am gonna append it to list when the opposite condition comes.
3 problems: 1) The variable hola was being incremented but not reset to 0 when a new deployment set started. This caused incorrect counting of features deployed on the same day.
2) The condition if day <= count was incorrect. It should be if day > count because if the current day is greater than the previous maximum day (count), it indicates a new set of features will be deployed.
3) The code was missing the handling of the last set of features deployed. It did not append the count of the last set to the answer list.
Biggest mistake is appending hola when hola is 0.
Wrong initial code:
import math
def solution(progresses, speeds):
# queue = deque(progresses)
hola=0
count=0
answer = []
for progress,speed in zip(progresses,speeds):
day = math.ceil((100-progress)/speed)
if day<=count:
hola+=1
count=day
continue
else:
answer.append(hola)
return answer
So correct code is
import math
def solution(progresses, speeds):
count = 0
hola = 0
answer = []
for progress, speed in zip(progresses, speeds):
day = math.ceil((100 - progress) / speed)
if day <= count:
hola += 1
else:
count = day
if hola > 0:
answer.append(hola)
hola = 1
answer.append(hola) # Append the count of the last set
return answer
or
def solution(progresses, speeds):
count = 0
hola = 0
answer = []
for progress, speed in zip(progresses, speeds):
day = math.ceil((100 - progress) / speed)
if day > count:
count = day
if hola > 0:
answer.append(hola)
hola = 0
hola += 1
answer.append(hola) # Append the count of the last set
return answer
Or you can append hola right away and edit that element in list like
def solution(progresses, speeds):
count=0
answer = []
for progress,speed in zip(progresses,speeds):
day = math.ceil((100-progress)/speed)
if day>count:
count=day
answer.append(0)
# editing last element in list
answer[-1]+=1
return answer
Or you can edit progresses list with increasing day number like diagram here https://happy-obok.tistory.com/38 Code:
def solution(progresses, speeds):
#결과를 담을 리스트
answer = []
#작업 리스트가 빌 때까지 반복
while progresses :
#몇개의 기능이 배포되는지 저장
cnt = 0
#작업 리스트가 남아있고 맨 앞의 작업의 진도가 100인 경우: 기능 배포 변수 증가. 해당 작업과 작업 속도를 리스트에서 제거
while progresses and progresses[0] >= 100:
cnt+=1
progresses.pop(0)
speeds.pop(0)
# 작업 리스트의 진도를 증가
progresses = [progresses[i]+speeds[i] for i in range(len(progresses))]
#만약 오늘 기능이 배포되었다면 결과리스트에 추가
if cnt:
answer.append(cnt)
return answer
I always sturggled taking care of the last case not being handled by my logic My code would have been like
def solution(progresses, speeds):
answer = []
time = 0
count = 0
while len(progresses)> 0:
if (progresses[0] + time*speeds[0]) >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
answer.append(count)
count = 0
time += 1
# taking care of last case
answer.append(count)
return answer
But I guess the code on top is better cuz it handles last case by placing
variable count within the while loop
프로세스
https://school.programmers.co.kr/learn/courses/30/lessons/42587
While my thinking is right, if there are duplicate values of same priority in queue, it gets whatever that value comes first in the list.
Wrong code
def solution(p, location):
maxCount = max(p)
q = p.copy()
while q:
if q[0]<maxCount:
q.append(q.pop(0))
else:
break
ori_value = p[location]
return q.index(ori_value)+1
Correct code:
from collections import deque
def solution(p, location):
maxCount = max(p)
queue = deque([(v, i+1) for i, v in enumerate(p)])
count = 1
while True:
v, i = queue.popleft()
if v < maxCount:
queue.append((v, i))
else:
if i == location + 1:
return count
count += 1
maxCount = max(queue)[0]
Or you can use any() like
def solution(priorities, location):
queue = [(i,p) for i,p in enumerate(priorities)]
answer = 0
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == location:
return answer
주식가격
https://school.programmers.co.kr/learn/courses/30/lessons/42584 oH i misunderstood the question. Once you see a price that is lower than the current price that is popped off, we only consider that duration. Even if there is a higher price later on in the queue, we don’t consider that. So we break out of the loop instead of continue. Before we break out of the loop, we increment count because when time=0, it is considered meeting the condition. Wrong code:
from collections import deque
def solution(prices):
queue = deque(prices)
answer = []
while queue:
price = queue.popleft()
count=0
for q in queue:
if q>=price:
count+=1
else:
continue
answer.append(count)
return answer
You should not continue when exception is occurred. Instead, you should break out of loop like
correct:
from collections import deque
def solution(prices):
queue = deque(prices)
answer = []
while queue:
price = queue.popleft()
count = 0
for q in queue:
if q >= price:
count += 1
else:
count += 1
break
answer.append(count)
return answer
Correct code
from collections import deque
def solution(prices):
queue = deque(prices)
answer = []
while queue:
price = queue.popleft()
count=0
for q in queue:
count+=1
if price>q:
break
answer.append(count)
return answer
using stack
def solution(prices):
answer = [0] * len(prices)
stack = []
for i in range(len(prices)):
while stack != [] and stack[-1][1] > prices[i]:
past_idx, _ = stack.pop()
answer[past_idx] = i - past_idx
stack.append([i, prices[i]])
for i, _ in stack:
answer[i] = len(prices) - i - 1
return answer
다리를 지나는 트럭 (hard)
https://school.programmers.co.kr/learn/courses/30/lessons/42583
This is the question where you implement the way a human would solve this problem. You actually create a queue bridge of 0s of length bridge_length. And append and pop the truck accordingly
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = [0 for _ in range(bridge_length)]
queue = deque(bridge)
waiting = deque(truck_weights)
time = 0
bridge_weight=0
while len(waiting)>0 or bridge_weight>0:
cur_weight = queue.popleft()
bridge_weight-=cur_weight
if waiting and bridge_weight+waiting[0]<=weight:
bridge_weight+=waiting[0]
queue.append(waiting[0])
waiting.popleft()
else:
queue.append(0)
time+=1
return time
while bridge_weight>0: this is very important because as long as there is a truck in our queue bridge currently passing, it needs to finish crossing regardless of whether the waiting queue of all trucks is empty.
[Fix 25th June] fuck i keep misunderstanding this if waiting condition. If waiting means if there is any element left in our waiting queue, not the other way around where if it is empty.
두 큐 합 같게 만들기
initial thinking code
def solution(queue1, queue2):
pointer1 =0
pointer2=0
count =0
for i in range(len(queue1),len(queue2)):
sum1 = sum(queue1)
sum2 = sum(queue2)
if sum1==sum2:
return count
elif sum1<sum2:
if queue2[pointer2] > queue1[pointer1]:
queue1.append(queue2[pointer])
pointer1+=1
sum1+=queue2[pointer2]
count+=1
elif queue2[pointer2] < queue1[pointer1]:
queue2.append(queue1[pointer1])
pointer2+=1
sum2 += queue1[pointer1]
count +=1
else:
val1 = queue1.popleft()
queue1.append(val)
val2 = queue2.popleft()
queue2.append(val)
else:
if queue2[pointer2] > queue1[pointer1]:
queue1.append(queue2[pointer])
pointer1+=1
sum1+=queue2[pointer2]
count+=1
elif queue2[pointer2] < queue1[pointer1]:
queue2.append(queue1[pointer1])
pointer2+=1
sum2 += queue1[pointer1]
count +=1
else:
val1 = queue1.popleft()
queue1.append(val)
val2 = queue2.popleft()
queue2.append(val)
return count
correct: https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%EB%91%90-%ED%81%90-%ED%95%A9-%EA%B0%99%EA%B2%8C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Python we iterate up till 3 times the length of queue1, as explained by that link
from collections import deque
def solution(queue1, queue2):
answer = 0
queue1, queue2 = deque(queue1), deque(queue2)
sum1, sum2 = sum(queue1), sum(queue2)
for i in range(len(queue1)*3):
if sum1>sum2:
sum1-=queue1[0]
sum2+=queue1[0]
queue2.append(queue1.popleft())
answer+=1
elif sum2>sum1:
sum2-=queue2[0]
sum1+=queue2[0]
queue1.append(queue2.popleft())
answer+=1
else:
return answer
return -1