[프로그래머스] 고득점Kit (2) - 스택/큐 (파이썬)

1. 기능 개발 (Lv. 2)

# 기능개발
def solution(progresses, speeds):
    days = []
    for program, speed in zip(progresses, speeds):
        temp = (100-program) % speed
        days.append((100-program)//speed + 1 if temp else (100-program)//speed)

    answer = []
    count = 1
    start = days[0]
    for i, x in enumerate(days):
        if i+1 < len(days) and start >= days[i+1]:
            count += 1
        else:
            answer.append(count)
            if i + 1 < len(days):
                start = days[i+1]
            count = 1

    return answer

 

zip을 이용해서 남은 일 수 리스트를 만든다 (days)

시작 부분(start) 보다 작은 패키지들은 전부 한 번에 배포 (count : 배포할 패키지 개수)

---

2. 프린터 (Lv. 2)

# 프린터
from collections import deque


def solution(priorities, location):
    pri = deque((priorities[i], i) for i in range(len(priorities)))

    answer = 0
    while pri:
        now, index = pri.popleft()

        isAppend = False
        for nnow, nindex in pri:
            if now < nnow:
                isAppend = True
                break

        if isAppend:
            pri.append((now, index))
        else:
            answer += 1
            if index == location:
                return answer

 

[우선순위, 인덱스] 순으로 리스트를 만든다.

큐를 이용하여 popleft를 해가면서 우선순위 비교 (만약 우선순위가 다음 것이 크다면 뒤에 다시 추가)

우선순위가 가장 크다면 answer += 1, 현재 인덱스가 목표 인덱스(location)이라면 return answer

---

3. 다리를 지나는 트럭 (Lv. 2)

# 다리를 지나는 트럭
from collections import deque


def solution(bridge_length, weight, truck_weights):
    answer = 0

    truck = deque(0 for _ in range(bridge_length))
    truck_weights.reverse()

    now_weight = 0
    while truck_weights:
        answer += 1
        temp = truck.popleft()
        if temp != 0:
            now_weight -= temp
        if now_weight + truck_weights[-1] <= weight:
            t = truck_weights.pop()
            truck.append(t)
            now_weight += t
        else:
            truck.append(0)
    answer += bridge_length
    return answer


print(solution(2, 10, [7, 4, 5, 6]))

 

큐를 이용해서 1씩 증가하면서 while문을 반복한다.

문제에 정보가 너무 부족했다.

문제에는 트럭이 1초에 다리길이 1만큼 이동한다는 말도 없었고, 트럭이 순서대로 다리를 지나야 한다는 말도 없었다.

문제를 풀면서 숨겨진 보기를 발견해가면서 풀었다..

---

4. 주식가격 (Lv. 2)

# 주식가격
def solution(prices):

    answer = [0 for _ in range(len(prices))]
    stack = []
    for i, pri in enumerate(prices):
        while stack and prices[stack[-1]] > pri:
            index = stack.pop()
            answer[index] = i - index
        stack.append(i)

    while stack:
        index = stack.pop()
        answer[index] = len(prices) - 1 - index

    return answer

 

이중 for문으로도 풀 수 있던 문제였다.

고득점 Kit의 취지에 맞게 스택으로 풀었다. 다만 스택으로 풀 경우 조금 어려웠다.

값이 아닌 index를 가지고 장난을 치는 문제다.

index를 stack에 push를 해주면서 prices [i]가 스택의 마지막 값보다 작으면

stack에서 pop을 하고 answer에 i - index를 취해준다. (현재 인덱스에서 이전 인덱스를 뺀 값)

answer는 이를 이용해서 추후에 len(prices) - 1 - index 값을 가지게 된다. (전체 길이 -1에서 현재 인덱스를 뺀 값)