KBR's Stacked Thoughts

1
2
3
4
5
6
7
8
9
10
11
from collections import deque

def solution(arr):
    ### 1. 큐 정의
    queue = deque()
    
    ### 2. 연속으로 나타나는 숫자 제거
    for num in arr:
        if not queue or queue[-1] != num:
            queue.append(num)
    return list(queue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import math

def solution(progresses, speeds):
    result = []
    
    ### 1. 작업별 완료까지 걸리는 날짜 계산
    days_required = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
    
    ### 2. 배포 그룹 묶기
    current_max_day = days_required[0]
    count = 1
    
    for day in days_required[1:]:
        if day <= current_max_day:
            count += 1             # 같은 배포 그룹
        else:
            result.append(count)   # 지금까지 묶인 개수 저장
            current_max_day = day  # 새로운 배포 기준일 갱신
            count = 1              # 초기화
    result.append(count)
    
    return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(s):
    stack = []
    for i in s:
        # 스택이 비어있는데 ')'가 들어오는 경우 >> False
        if len(stack) == 0 and i == ')':
            return False
        # 스택에 열린 괄호가 들어오는 경우 >> append
        if i == '(':
            stack.append('(')
        # 스택 맨 위에 '('가 있는데 닫힌 괄호가 들어오는 경우 >> pop
        if stack[-1] == '(' and i == ')':
            stack.pop()
    # 스택에서 '()'를 다 제외했는데 괄호가 남아있는 경우 >> False
    return False if len(stack) != 0 else True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque

def solution(priorities, location):
    ### 1. 큐 정의
    queue = deque([(i, p) for i, p in enumerate(priorities)])
    answer = 0
    
    while queue:
        idx, priority = queue.popleft()
        # 더 높은 우선순위가 있다면 큐에 다시 넣기
        if any(priority < other_priority for _, other_priority in queue):
            queue.append((idx, priority))
        else:
            # 종료한 프로세스의 수 ++
            answer += 1
            # location과 같다면 리턴
            if idx == location:
                return answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import deque

def solution(bridge_length, weight, truck_weights):
    ### 1. 큐 정의
    bridge = deque([0] * bridge_length)
    # 트럭의 무게 배열도 큐로 변경 (시간 최적화)
    # 파이썬의 일반 리스트 `list`에서 `pop(0)`을 쓰면 O(n)의 시간이 걸리는데,
    # deque는 `popleft()`의 연산이 O(1)로 매우 빠름
    truck_weights = deque(truck_weights)
    answer = 0  # 시간
    total_weight = 0
    
    ### 2. bridge 큐가 비어있지 않을 때까지 시간을 증가시키면서 반복문 수행
    while bridge:
        answer += 1
        
        # 한 칸 전진 (맨 앞 트럭 빼기)
        total_weight -= bridge.popleft()
        
        # 건너야 할 트럭이 남아있다면
        if truck_weights:
            ### 3. 다음 트럭도 건널 수 있다면
            if total_weight + truck_weights[0] <= weight:
                # 다음 트럭을 다리로 이동
                truck = truck_weights.popleft()
                bridge.append(truck)
                total_weight += truck
            # 트럭 무게를 초과한다면 다리에 빈 공간 넣기
            else:
                bridge.append(0)
        
    return answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(prices):
    answer = [0] * len(prices)
    ### 1. 여기에는 "가격이 아직 떨어지지 않은 시점의 인덱스" 저장
    stack = []
    
    for i in range(len(prices)):
        ### 2. 스택에 값이 남아있고, 가격이 떨어진 경우
        while stack and (prices[i] < prices[stack[-1]]):
            top = stack.pop()
            answer[top] = i - top
        ### 3. 가격이 떨어지지 않았으면 현재 시점의 인덱스 append
        stack.append(i)
    
    ### 4. 끝까지 가격이 떨어지지 않은 경우 (스택에 값이 남아있는 경우)
    while stack:
        top = stack.pop()
        answer[top] = len(prices) - 1 - top
        
    return answer