스택/큐 (STACK/QUEUE)

 

 

 

스택(stack)은 쌓아 올린다는 뜻으로, 자료를 쌓아 올린 형태의 구조를 말한다.

 

스택(stack)

- 맨 위 요소만 접근 가능

- 데이터를 push하면 top에 들어가고, pop하면 가장 최근에 푸시한 데이터가 나온다.

- LIFO (Last In First Out) 구조이다. (후입선출)

 

 

스택

장점 

- 데이터의 삽입과 삭제가 빠름.

 

단점

- 맨 위의 원소만 접근 가능

 

 

 

 

큐(queue)는 무엇을 기다리는 사람의 사전적 정의를 가지고 있으며, 먼저 들어간 데이터가 먼저 나가는 것에서 붙여졌다.

큐

- 데이터가 push되는 곳을 front, pop되는 곳을 back이라 함.

- FIFO (First-In-First-Out) 구조이다. (선입선출)

 

 

큐

 

다음과 같다.

 

 

 

[프로그래머스] 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

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

 

 

 

풀이)

스택 / 큐의 풀이유형은 대체로 비슷한 내용이다. bridge의 길이만큼 0을 채운 다음에 pop을 이용해 선입선출로 진행한다.

만약 truck_weights 와 다리의 무게 합이 주어진 weight보다 작거나 같으면 첫 번째 들어간 트럭의 무게를 또 없애준다.