스택/큐 (다리를 지나는 트럭)

이번 문제는 처음부터 삽질을 많이 한 결과로 볼수가 있다ㅠ

stack & queue에 대한 개념을 먼저 잡아야 했고, 다리를 통과하는 것은 stack보다는 queue가 더

적합한 것 같아서 queue를 통해 구현하기로 했다.

 

*기본적인 stack 선언

Queue temp = new LinkedList();

Queue는 LikedList 형태로 구현이 되어있고, array와 같은 개별적으로 존재하는 것이 아닌 값들이 서로

연결되어있어 메모리의 빈 공간을 차지하지 않는다는 장점이 있다.

하지만 장점이 있으면 단점이 있다는 것인데, 자료값을 search 하거나, 삽입, 삭제 등을 할 때 시간이 걸린다.

array는 int arr[4] = 0; 같이 직관적으로 삽입할 수 있으니!!

 

▶위 문제를 먼저 분석해본결과

1. truck array -> truck_queue에 삽입하고

2. truck_queue에서 bridge_queue로 넣을 때 (현재 bridege_queue + truck_queue 맨 앞 값 <= weight 이어야 함)

3. queue안에 있는 값들은 (bridge를 이동하는 값, 전체시간을) 1cycle마다 1씩 증가 시켜야 함.

4. bridge 길이를 통과하면 queue의 맨 앞에 있는 트럭을 poll() 처리

5. truck_queue와 bridge_queue가 비어있을 때 까지 진행

 

▶사용한 함수

add() -> queue에 값을 추가

poll() -> queue에서 맨 앞 값을 꺼냄

peek() -> queue 맨 앞 값을 꺼내지는 않고 맨 앞의 값 확인

is.Empty() -> 스택이 비어있는지 확인하는 함수

 

*처음에 전체적인 시간에서 bridge 길이만큼 1cycle마다 1씩 증가시켰는데, 트럭이 1초 간격으로 들어왔을 때

1초 후에 나가는 것이 아니라, bridge 길이만큼 시간을 두고 탈출하였다. (이것이 삽질,,,)

 

*그래서 queue에 값 1개를 넣는 것이 아닌, (트럭무게, 다리이동시간)의 2개를 가질 수 있는 queue를 구글링 했고

Point Queue를 찾았다.

 

*Point Queue

Queue <Point>temp = new LinkedList<Point>();

 

간편하게 Point 형식의 구조체를 제공해서,, 글에서 잠깐 봤을 때는 그래프 등을 그릴 때 쓰인다는 것 같은데

Point.x / Point.y의 형태로 x,y 값을 쉽게 가지고 오고 변경 시킬수도 있다.

나는 2부분을 따로 함수로 빼서 만들었는데

 

1. queue안에 있는 y값 (다리이동시간)을 전체적으로 1씩 증가시키는 함수

-> queue에서 모든 값을 증가시키는 함수가 없어, 일시적인 temp_queue에 넣어놓고 다시 bridge_queue에 넣었다.

 

2. queue안에 있는 x값 (트럭무게)를 다 합산한 총 무게를 return 하는 함수

-> 이것도 queue 안에 있는 값을 한개씩 불러오려면 poll()로 queue에서 빼내야하기 때문에 다시 bridge_queue에 넣었다.

 

*출처 : programmers.co.kr/learn/courses/30/lessons/42583