스택/큐
LIFO, FIFO, push & pop! 스택과 큐를 이용해서 문제를 풀어보세요.
| 출제 빈도 | 평균 점수 | 문제 세트 |
|---|---|---|
| 보통 | 높음 | 6 / 6 |
같은 숫자는 싫어
def solution(arr):
a = []
for x in arr:
if a[-1:] != [x]:
a.append(x)
return a풀이
연속적으로 나타나는 숫자는 하나만 남기고 제거하면 된다.
스택을 사용하되, 연속적으로 나타나는 숫자인지 판단하는 것은 [-1:]을 사용했다.
[-1:]은 [-1]과 유사한 알고리즘(?)이다.
[-1]은 리스트의 맨 뒤의 값을 가져오는 것이다.
[-1:]에서 :이 의미하는 것은, 리스트 형태로 반환하겠다는 의미이다.
처음에 [-1]로 비교했었는데,
맨 처음에는 리스트에 아무런 값도 없기 때문에 list index out of range 오류가 발생한다.
뭐, 리스트 초기화 할 때 0 또는 음수를 넣고, [-1]로 비교한 뒤에 a.pop(0)을 호출하고 return a 해도 되지만 그냥 간단하게 [-1:]로 하자.
기능개발
코드 #1
def solution(progresses, speeds):
answer = []
stk = [] # 배포되는데 필요한 일 수를 저장하는 스택(리스트)
for progress, speed in zip(progresses, speeds):
left_progress = 100 - progress # 남은 작업 %
deploy = left_progress // speed if left_progress % speed == 0 else left_progress // speed + 1 # 배포되는데 필요한 일 수
stk.append(deploy)
prev = stk[0]
count = 0 # 각 배포마다 몇 개의 기능이 있는지
for i in range(len(stk)):
if stk[i] > prev:
answer.append(count)
count = 1
prev = stk[i] # 다음 비교를 위해 갱신
else:
count += 1
answer.append(count) # 마지막 배포에 포함되는 기능 개수 추가
return answer코드 #2
import math
def solution(progresses, speeds):
answer = []
progresses = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
n = len(progresses)
front = 0
for idx in range(n):
if progresses[idx] > progresses[front]: # 배포 일수가 더 크다면
answer.append(idx - front) # 차이만큼 추가(= 배포되는 개수)
front = idx # 갱신(다음 비교를 위해)
answer.append(n - front) # 마지막 배포 추가
return answer풀이
아이디어: 소요되는 시간 리스트에서
작은 값 -> 큰 값으로 변할 때가 기준이 됨을 찾아야 한다.
두 코드는 전반적으로 동일한 로직을 가진다.
문제를 푸는 아이디어를 살펴보자.
예를 들어 입/출력이 아래와 같다고 하자.
| progresses | speeds | return |
|---|---|---|
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
이때, 각 기능이 배포되는데 소요되는 시간을 구해보면 [7, 3, 9] 이다.
소요되는 시간 과 return 을 보면,
맨 첫번째 원소부터 시작해서 현재 원소보다 다음의 원소의 값이 더 클 경우 하나의 개수로 설정한다.
예를 들어 소요되는 시간이 [7, 3, 9] 일 때,
7일 때, 7은 첫번째이므로 넘긴다.
3일 때, 3은 7보다 작으므로 배포를 아직 하지 못한다.
9일 때, 9는 3보다 크므로 9보다 앞에 있는 것들이 배포가 된다.
즉, [7,3] 2개가 배포가 된다.
그리고 마지막 기능의 배포는 for문에서 추가하지 못하므로
for문이 끝난 후 추가해준다.
[7, 3, 9]=>[(7, 3) / (9)]
[5, 10, 1, 1, 20, 1]=>[(5) / (10, 1, 1) / (20, 1) ]
올바른 괄호
def solution(s):
answer = True
stk = []
for x in s:
if x == '(': # '('라면 그냥 넣어준다.
stk.append('(')
else:
if not stk: # 스택이 비어있다면
return False
else: # '('를 제거한다.
stk.pop(-1)
return not stk # 스택이 비어있는지 -> 빈다 : True, 차있다 : False풀이
코딩 테스트를 준비했으면 많이 접해봤을 문제이다.
내가 생각한 올바른 괄호를 판단하는 기준은,
최종적으로 stk 리스트가 비어있는 경우이다.'('는 그대로 넣어주고,')'인 경우에는'('을 삭제한다.
만약, 스택이 비어있는데 ')'라면, 올바르지 않은 괄호이므로 return False 이다.
stk.pop(-1)이 동작하는 근거는, '('만 stk에 넣어주기 때문이다.
그래서 stk이 비어있지 않다면, 항상 '(' 만 들어가있는 것이다.
프로세스
from collections import deque
def solution(priorities, location):
q = deque([(i, p) for i, p in enumerate(priorities)]) # (위치, 우선순위) deque
count = 0
while True:
i, p = q.popleft()
if any(p < x[1] for x in q): # 자신보다 우선순위가 더 높은 프로세스가 있다면
q.append((i, p)) # 큐에 다시 넣는다.
else: # 그런 프로세스가 없다면
count += 1 # 실행 번호 + 1
if i == location: # 알고자 하는 프로세스의 위치라면
break # 종료
return count
풀이
처음 문제를 보자마자, priorities 리스트에 우선순위가 같은 프로세스가 존재할 수 있으므로,
각 위치를 저장하는 것도 필요하다고 생각했다.
메인 로직은 다음과 같다.
deque 를priorities의 (인덱스, 우선순위) 로 초기화한다.
인자로 주어진 location과 같은 인덱스를 가지는 프로세스를 꺼낼때 까지 계속해서 while문을 반복한다.
이때 자신보다 우선순위가 높은 프로세스가 있는지 확인해야 하는데, 이는 any() 를 사용해서 판단했다.
any(...): 인자로 들어가는 표현이 하나라도 true가 있으면 true를 return한다.
만약, 우선순위가 높은 프로세스가 없다면, 실행 횟수를 1 증가 시키고,
현재 꺼낸 프로세스의 인덱스와 인자로 주어진 location 을 비교한다.
만약, 같다면 우리가 원하는 프로세스이므로 while문을 종료한다.
아니라면 원하는 프로세스를 찾을 때 까지 반복한다.
다리를 지나는 트럭
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 0 # 총 흐른 시간
q = deque([0 for _ in range(bridge_length)]) # 다리
_sum = 0 # 다리를 건너는 트럭 무게의 총 합
while q:
answer += 1 # 시간 흐른다.
_sum -= q.popleft() # 다리를 지난 트럭(다리의 길이를 1만큼 빼준다)
if truck_weights: # 대기하는 트럭이 있을 때
if _sum + truck_weights[0] <= weight: # 다리를 건너는 트럭과 대기하는 첫번째 트럭의 무게를 견딜 수 있다면
truck = truck_weights.pop(0) # 대기하는 트럭 제거
q.append(truck) # 제거한 트럭을 다리에 올린다.
_sum += truck # 다리를 건너는 트럭 무게의 합
else: # 견딜 수 없다면
q.append(0) # 0을 추가해서 다리의 길이를 맞춘다.
return answer풀이
설명이 약간 불친절 했다.
bridge_length 가 의미하는 바는 아래와 같다.
다리에 올릴 수 있는 트럭의 개수다리의 길이
즉, bridge_length == 3 이면
- 트럭이 다리를 건너기 위해 필요한 시간은
3초 - 다리에 올릴 수 있는 트럭의 개수는
3대
q는 다리를 의미하는데, 처음에는 모두 0으로 채워준다.
(이는 다리의 길이를 유지하기 위함이다.)
다시 말하면, 0이라면 트럭이 올라와 있지 않은 칸을 의미하고, 0이 아니라면 현재 트럭이 위치한 칸을 의미한다.
메인 로직은 다음과 같다.
- 다리가 비지 않을때 까지(= 길이가 0이 아닐때 까지)
1.1 1초의 시간이 흐른다.
1.2 다리를 지난 트럭을 빼준다(있으면 해당 트럭의 무게, 아니면 0)
1.3 대기하는 트럭이 있다면- 첫번째 대기하는 트럭 무게와 현재 다리가 견디는 무게의 합이 다리가 견딜 수 있는 무게의 합보다 작거나 같다면, 대기하는 트럭을 다리에 올리고, 다리가 견디는 무게를 갱신한다.
- 아니라면,
q(다리)에 0을 추가해서 길이를 맞춘다.
주식가격
코드 #1
def solution(prices):
n = len(prices)
answer = [0] * n # 가격이 떨어지지 않은 기간을 담는 리스트
for i in range(n - 1):
for j in range(i + 1, n):
answer[i] += 1 # 시간 증가
if prices[j] < prices[i]: # 주식 가격이 떨어졌다.
break # 다음 주식을 비교하기 위해
return answer풀이
설명이 필요없이 로직은 단순하다.
이중 for문으로 현재 주식과 다음 주식의 가격을 비교해서 가격이 떨어지지 않은 기간을 계산하면 된다.
그러나 시간복잡도에서 의문이 생겼다.
문제에서 prices의 길이는 최대 100,000이다.
시간복잡도는 인데 왜 통과가 되는걸까?
코드 #2
def solution(prices):
length = len(prices)
answer = [ i for i in range (length - 1, -1, -1)]
stack = [0]
for i in range (1, length, 1):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer풀이
다른 효율적인 코드를 찾다가, 효율성 측면에서 소요 시간이 많이 줄어드는 코드를 찾았다.
대략 5배? 정도 덜 걸리는 것 같다.
설명 추가는 추후에..
