문제
https://www.acmicpc.net/problem/1863
접근
- 건물 겉넓이, 빗물 트래핑, 주식 매매 같은 문제랑 비슷한 거 같아서 스택으로 풀이했다.
풀이
- 입력받은 y에 대해 스택에는 y보다 낮은 높이의 건물만 있도록 pop하면서 ans에 1씩 더한다.
- y가 스택에 있는 마지막 요소랑 같거나 0인 경우에는 스킵하고, 더 작은 경우 append한다.
- 모든 입력을 처리한 후 스택에 남아있는 원소들을 pop하면서 ans에 1씩 더한다.
n = int(input())
stack = []
ans = 0
for _ in range(n):
x, y = map(int, input().split())
while stack and stack[-1] > y:
stack.pop()
ans += 1
if y == 0:
continue
if not stack or stack[-1] < y:
stack.append(y)
while stack:
stack.pop()
ans += 1
print(ans)
'Python > Coding Test' 카테고리의 다른 글
22871 징검다리 건너기 (large) (0) | 2022.02.27 |
---|---|
22869 징검다리 건너기 (small) (0) | 2022.02.27 |
20182 골목 대장 호석 - 효율성 1 (0) | 2022.02.25 |
21277 짠돌이 호석 (0) | 2022.02.24 |
10703 유성 (0) | 2022.02.24 |