[알고리즘 테스트] 스택/큐 문제모임 및 풀이

Introduction 

최근 알고리즘 테스트를 하면서 느낀점은 시뮬레이션, DFS/BFS는 그래도 손에 익기 시작했는데 아직까지 Stack과 큐의 문제만 나오는 경우에서는 잘 못 푸는 나의 모습을 발견하였다.. 

 

이번에 공부를 하면서 스택/큐의 개념에 대해서 다시 공부를 하였으며 어떠한 방법들이 있는지 다시 되돌아볼수 있었다. 

 

많은 블로그를 참고를 하였지만 결국 개념은 스택의 경우는 FILO(First in Last out) 큐의 경우는 FIFO(First in First out)이라는 것을 명심해두자. 

 

Solution

아직 많이 부족한 나지만 문제를 풀다보면 스택과 큐를 풀수 있는 실마리를 찾는게 매우 중요하다.

또한 스택/큐 로 풀면 되겠다고 생각하더라도 문제 해결과정을 머리에서 빨리 돌아가야지 풀수있다. 

 

그렇기에 내가 빨리 풀수 있다고 느낀점은 다음과 같았다. 

1. 효율성을 생각해보기 

2. 그림으로 그려보기

 

첫번쨰 효율성의 경우에서는 보통 샘플이 10,000 이하로 주는 경우가 많다. 이경우에서는 단순하게 $O(N^2)$로 생각해보면 time complexity가 높겠네 생각이 들기 마련이다. 

그렇게 되면 스택, 큐, 해시로 풀수 있겠네라고 생각해볼수 있따. 

두번째는 확실하게 느낀점이지만 그림으로 그리면 쉽게 생각이 되어진다. 스택과 큐의 그림은 쉽게 그릴수 있지만 직접그려본 사람이 없지 않는가라고 생각이 든다. 

그렇기 떄문에 고수가 아닌이상 그리면서 문제를 풀어보자. !!

 

Problem

내가 스택을 이용해서 푼 문제들은 프로그래머스의 고득점 Kit에서 참고하여 풀었다 .

Level2이상은 대부분 코테에서 통과할만한 수준이라고 하여서 해당방법 위주로 정리하였다.

 

문제1 : https://school.programmers.co.kr/learn/courses/30/lessons/42586 기능개발 

프로그래머스

해당문제의 경우에서는 

작업 개수에 걸린 시간과 그에 따른 시간을 측정해서 최종 시간을 return하는 문제이다. 

내가 푼 방법은 Stack으로 풀었기 떄문에  그방법을 공유해본다

import math
def solution(progresses, speeds):
    ## 일단 progress당 걸리는 시간을 미리 계산해보자. 
    work_days = [math.ceil((100 - progress)/work_time) \
        for progress, work_time in zip(progresses, speeds)] # 소요시간 미리 계싼
    
    if len(work_days) == 1: # 만약에 하나라면 지금 걸리는 시간 출력
        return [work_days[0]]
    
    front = 0 
    answer = []
    for idx, _ in enumerate(work_days): 
        if work_days[idx] > work_days[front]: # 앞으로 온다음에 CUT!!!
            answer.append(idx-front)
            front = idx
    answer.append(len(work_days) -  front)
    return answer

그림으로 그리면 Stack의 형태로 그려진다. 

만약 `Work_days` 라는 변수가 [7,3,9]라고 나온다고 하면 최종 return 은 [2,1]로 나온다. 

7,4,9를 stack으로 만들어서 넣으면 되다

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

 

문제풀이 

중요한건 다리를 큐로 생각하고 진행한다는점 

 

from collections import deque
def solution(bridge_length, weight, truck_weights):
    
    # 2개의 큐 구조를 사용해서 문제를 풀어보자. 
    q = deque(truck_weights)
    weight_q = deque([0] * bridge_length) # 다리를 큐 모양으로 만들자. 
    curr_weigth = 0 
    answer = 0 
    
    while q : # bright 작동
        answer += 1

        curr_weigth -= weight_q.popleft()
        if curr_weigth + q[0] <= weight:
            curr_weigth += q[0]
            weight_q.append(q.popleft())
        else: 
            weight_q.append(0)
            
    answer += bridge_length
    return answer