[백준 17608] 막대기

문제

N개의 막대기를 왼쪽부터 일렬로 세운 후에 오른쪽에서 바라보았을 때 몇 개의 막대기를 볼 수 있는지 구해보자.

일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다.

 

입력

첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다.

 

출력

오른쪽에서 N개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다.

---

접근

오른쪽에서 보기 때문에 가장 오른쪽에 있는 막대기는 무조건 볼 수 있다. 이후 가장 오른쪽에 있는 막대기의 높이를 기준으로 최댓값을 갱신하여 볼 수 있는 막대기를 구한다.

 

구현

- 입력받은 막대기의 높이를 뒤집어서 순차적으로 탐색한다.

- 스택이 비어있으면 현재 막대기를 스택에 넣고 최종해를 1 증가시킨다.

- 스택의 top과 현재 막대기의 높이와 비교해서 현재 막대기의 높이가 크다면 볼 수 있기 때문에 

- 스택 pop 후에 현재 막대기를 push한다. 

- 그리고 최종해를 1 증가시킨다.

for stick in reversed(stick_list):
    if stack:
        if stack[-1] < stick:
            stack.pop()
            stack.append(stick)
            answer += 1
    else:
        stack.append(stick)
        answer += 1

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
stick_list = []
for _ in range(N):
    stick_list.append(int(input()))

answer = 0
stack = []
for stick in reversed(stick_list):
    if stack:
        if stack[-1] < stick:
            stack.pop()
            stack.append(stick)
            answer += 1
    else:
        stack.append(stick)
        answer += 1

print(answer)