백준 17608 - 막대기 (파이썬)

https://www.acmicpc.net/problem/17608

풀이

여러개의 막대기가 일렬로 세어져 있을 때, 오른쪽에서 보았을때 보이는 막대기의 개수를 구하는 문제이다.

• 막대기는 왼쪽에서 오른쪽으로 나열되어 있으며, 각 막대기의 높이가 주어진다.
• 오른쪽에서 왼쪽을 바라볼 때, 더 높은 막대기가 나오지 전까지의 막대기만 보이게 된다.

for i in range(N - 1, -1, -1):  # 오른쪽에서 왼쪽으로 순회
    if max_height < H[i]:  # 현재 막대기가 기존 최고 높이보다 높으면
        max_height = H[i]  # 최고 높이 갱신
        count += 1  # 보이는 막대기 개수 증가

오른쪽에서 왼쪽으로 막대기 리스트를 탐색한다.

만약 현재 막대기의 높이가 max_height 보다 크다면, 이는 새로운 보이는 막대기 이므로, count를 증가시킨다.

max_height를 현재 막대기의 높이로 갱신한다.

시간 복잡도 분석

• 한번의 순회만 이용하므로 O(N)

코드

# 백준 17608 - 막대기
# 분류 : 구현

import sys
input = sys.stdin.readline

N = int(input())
H = [0] * N

for i in range(N) :
    H[i] = int(input())

max_height = 0
count = 0
for i in range(N - 1, -1, -1) :
    if max_height < H[i] :
        max_height = H[i]
        count += 1

print(count)