백준 - 17608 막대기

이 문제는 스택으로도 풀 수 있고 덱으로도 풀 수 있는 문제이다.

나는 덱으로 풀었다.

이유는 덱으로 스택을 구현할 수 있기 때문에 굳이 스택을 사용안했고 덱을 공부하고 있기 때문에 덱을 사용하였다.

문제에 나온 것 처럼 막대기를 오른쪽 방향에서 봤을 때 막대기가 몇 개 보이는지 구하는 문제이다.

예를 들어 6 6 9 7 6 4 6 을 오른쪽에서 본다면 제일 앞에 나와있는 6길이의 막대기보다 작은 길이의 막대기는 보이지 않는다. 따라서 6보다 큰 7과 9길이의 막대기만 보인다.

나는 deque에 막대길의 길이를 다 넣고 가장 긴 길이의 막대기와 비교하면서 answer값을 1씩 증가시켰다.

최장길이 : 6 -> 4 -> 6 -> 7 -> 9 -> 6 -> 6
answer : 1 -> 1 -> 1 -> 2 -> 3 -> 3 -> 3

-> 이 문제의 포인트는 최장길이를 업데이트 해주어야한다.

5 5 4 3 2 1을 보자 deque에서 가장 먼저 pop된 1은 현재 가장 최장길이이다.

하지만 pop을 한 번 더 하면 최장길이는 2로 바뀌어야 한다. (이 때 answer값을 1증가시킨다)

최장길이 : 1 -> 2 -> 3 -> 4 -> 5
answer : 1 -> 2 -> 3 -> 4 -> 5