[PROGRAMMERS] 프로그래머스 코딩테스트 연습 > 스택&큐(stack&queue) 파이썬 문제풀이

프로그래머스 코딩테스트 연습 > 고득점 kit > 스택&큐(stack&queue) 파트 문제풀이 파이썬.ver https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

 

스택(Stack) & 큐(Queue)

 

 스택(Stack) 

출처 https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

LIFO(Last Input First Out, 후입선출)

마지막으로 넣은 데이터가 가장 먼저 나오는 자료구조

한쪽 방향으로만 삽입(push), 삭제(pop)하며 가장 위의 데이터만 접근 가능

자료가 없을 때 pop 하면 stack underflow, 스택의 크기 이상의 자료를 push 하려고 할 때의 오류 stack overflow

 

예) 웹 브라우저 방문기록, 이전 실행 취소, 수식의 괄호 검사, 시스템 스택 등

 

실행시간 : 삽입, 삭제 O(1) / 탐색 O(n)

 

 

 큐(Queue) 

출처 https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

FIFO(First-In-First-Out, 선입선출)

먼저 넣은 데이터가 먼저 나오는 구조

양방향으로 접근하여 한쪽 방향으로 데이터를 삽입(enqueue)하고 다른 방향으로 데이터를 꺼냄(dequeue)

 

예) 정해진 순서대로 일을 처리해야하는 경우 주로 사용, 너비우선탐색(BFS), 프로세스 관리 등

 

실행시간 : 삽입, 삭제 O(1) / 탐색 O(n)

 

 

기능개발 (Level.2)

처음에 문제 해석이 조금 어려웠었다.

중요한 부분은 뒤의 기능이 앞에 나온 기능보다 빨리 개발될 순 있지만 앞의 기능이 배포될 때 뒤의 기능도 같이 배포된다는 점!

즉 먼저 들어온 것이 먼저 나감으로 FIFO 큐를 사용해야 한다.

 

사실 잘 모르겠어서 이건 다른 사람들 코드를 참고해서 풀었다.

 

내 코드 + 다른 사람 코드 1

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

    answer.append(count)
            
    return answer

다른 사람 코드 2

def solution(progresses, speeds):
    Q = []
    for p, s in zip(progresses, speeds):
        if len(Q) == 0 or Q[-1][0] < -((p-100) // s):
            # 첫번째 반복문을 돌 때, -와 //로 올림연산
            Q.append([-((p-100) // s), 1]) # [첫번째 기능 개발에 필요한 날짜, 1]
        else:
            Q[-1][1] += 1 # count, 앞의 기능 개발 날짜 안에 포함되면 배포될 기능 수 ++
    return [q[1] for q in Q]

 

 

프린터 (Level.2)

이 문제는 나에게 다른 문제들에 비해 그나마 좀 풀만했던 문제..

 

내 코드

def solution(priorities, location):
    answer = []

    docs = []
    find = ()

    for i, p in enumerate(priorities):
        docs.append((i, p)) # tuple(문서 인덱스, 우선순위)
        if i == location: # 정답을 위해 인쇄 순서를 찾아야하는 문서 tuple(문서 인덱스, 우선순위)
            find = (i, p)

    while len(docs) != 0:
        max_priority = max(p for _, p in docs) # 가장 중요한 문서 확인
        doc  = docs.pop(0) # 리스트에서 첫번째
        
        # doc = (문서 인덱스, 우선순위)
        if doc[1] < max_priority: # 우선순위가 낮을 때 맨뒤로 이동
            docs.append(doc)
        else: # 우선순위가 더 높거나 같을 때(가장 높거나 동일 시 순서가 더 앞일때) 인쇄 순서에 포함
            answer.append(doc)

    return answer.index(find) + 1 # answer 리스트에서 찾으려는 문서 tuple의 위치

먼저 인쇄할 문서들의 우선순위만 주어지기 때문에 enumerate() 를 이용하여 문서 인덱스와 우선순위 두 정보가 담긴 튜플들의 리스트로 문서들을 정리해줬다(docs).

location을 나중에 처리하려 했더니 튜플들이 담긴 리스트(docs)에 사용하기가 어려워 튜플 리스트를 만들때 인쇄 순서를 찾아야하는 문서의 튜플 자체를 미리 저장해두었다.

맨 첫번째 문서를 pop으로 꺼내서 나머지 문서들 중 우선순위가 가장 높은 것과 비교했다.

비교하여 우선순위가 더 낮으면 맨 뒤로 보냈고 우선순위가 더 높아 가장 높은 우선순위를 가진 문서라면 docs에서 빼서 answer에 추가, 인쇄 순서를 정해주었다.

마지막으로 위에서 저장한 location 에 해당하는 tuple의 인쇄 순서는 answer리스트에서 index() 메서드를 통해 순서를 반환하였다.

 

다른 사람 코드 1

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

다른 사람 코드 2

def solution(p, l):
    ans = 0
    m = max(p)
    while True:
        v = p.pop(0)
        if m == v:
            ans += 1
            if l == 0:
                break
            else:
                l -= 1
            m = max(p)
        else:
            p.append(v)
            if l == 0:
                l = len(p)-1
            else:
                l -= 1
    return ans

 

 

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

이 문제는 도저히 못풀겠어서 그냥.. 다른 사람 코드 참고하여 풀었다.

 

다른 사람 코드 1

from collections import deque

def solution(bridge_length, weight, truck_weights):
    on_bridge = [] # 다리 위
    sum_weight = 0
    time = 0

    while truck_weights:
        time += 1

        while on_bridge and on_bridge[0][0] <= time: # 건너고 있는 트럭이 있고, 가장 앞서있는 트럭이 다 건넜을 때
            print(time,' ', on_bridge)
            _, w = on_bridge.pop(0) # 맨 앞선 트럭 제거
            sum_weight -= w # 전체 무게에서 제거

        if sum_weight + truck_weights[0] <= weight: # 무게가 남을 때
            truck = truck_weights.pop(0) # 가장 먼저 있는 대기중인 트럭
            on_bridge.append((bridge_length + time, truck)) # tuple(추가된 트럭이 다리를 건너는데 걸리는 시간, 트럭 무게)
            sum_weight += truck # 다리 위 트럭들의 무게 합

    return on_bridge[-1][0] # 마지막 트럭의 시간

다른 사람 코드 2

import collections

DUMMY_TRUCK = 0

class Bridge(object):

    def __init__(self, length, weight):
        self._max_length = length
        self._max_weight = weight
        self._queue = collections.deque()
        self._current_weight = 0

    def push(self, truck):
        next_weight = self._current_weight + truck
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck)
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft()
        self._current_weight -= item
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight)
    trucks = collections.deque(w for w in truck_weights)

    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    while trucks:
        bridge.pop()

        if bridge.push(trucks[0]):
            trucks.popleft()
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1

    while bridge:
        bridge.pop()
        count += 1

    return count

def main():
    print(solution(2, 10, [7, 4, 5, 6]), 8)
    print(solution(100, 100, [10]), 101)
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)


if __name__ == '__main__':
    main()

다른 사람 코드 3

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

 

 

주식가격 (Level.2)

이 문제 또한 문제 설명이 모호해서 이해하는데 꽤 시간이 걸렸다 ㅠㅠ

질문 게시판을 참고해서 문제를 완벽히 이해했다. (참고 https://programmers.co.kr/questions/6948)

가격이 떨어지지 않은 기간은 처음 기준 가격이 시간이 지남에 따라 바뀐 가격과 비교했을 때 가격이 떨이지지 않았을 때까지 기간(시간)을 의미한다.

문제의 테스트케이스를 예를 들어 [1, 2, 3, 2, 3]가 주어졌을때

[0] 기준 가격이 1인 경우) 2, 3, 2, 3 와 비교했을 때 모두 가격이 높아 끝까지 가격이 떨어지지 않음으로 4

[1] 기준 가격이 2인 경우) 마찬가지로 3, 2, 3과 비교했을 때 가격이 모두 떨어지지 않음으로 3

[2] 기준 가격이 3인 경우) 다음 가격이 2로 가격이 떨어졌다. 따라서 가격이 떨어지지 않은 기간은 2가 되기 전까지임으로 1

이런식으로 계산이 된다.

 

내 코드

def solution(prices):
    answer = []
    time = 0
    length = len(prices)

    for i in range(length):
        time = 0
        for j in range(i+1, length):
            if prices[i] > prices[j]: # 가격이 떨어졌을 때
                break # 떨어진 가격전까지의 기간 구함
        answer.append(j-i)
        
    return answer

처음에 '가격이 떨어지지 않은 기간'을 그냥 가격이 떨어지지 않은 구간의 수를 구하라는 의미로 해석하여 break 대신 count를 증감시켰고 이를 반환했었다. 이렇게하면 문제의 테스트케이스만 통과되고 바로 틀린 답이라고 뜬다..

질문 게시판을 보니 나처럼 해석해서 틀리는 사람들이 꽤 있는 것 같다.

 

다른 사람 코드

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    
    while prices:
        c = prices.popleft() # pop(0) 가장 왼쪽(첫번째) pop
        count = 0
        for i in prices: 
            if c > i: # 가격이 떨어졌을 때
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

문제 취지에 맞게 큐를 잘 사용한 코드라고 생각한다. 나도 처음에 큐를 쓰고싶었는데 어찌저찌 짜다보니 안씀..