[백준] 파이썬 1863번: 스카이라인 쉬운거

 

 

 

 

# 요구사항 - 건물이 최소 몇개일지?
# 스택에 암것도 없음 -> 높이를 스택에 넣기 
# 스택에 넣어야 하는경우 - 아무것도 없을때. 현재높이 보다 더 높은 건물일때.
# 스택에 안넣어야 하는 경우 - 높이가 같을때.(중복)
# 스택에서 빼야하는 경우 - 높이가 낮아졌을때. 해당 건물이 끝났음.
import sys
input = sys.stdin.readline

n = int(input())
building = 0 # 건물 개수
stack = [] # 스택 선언
for i in range(n):
    x, y = map(int, input().split())

    while stack and stack[-1] > y: # 스택에 뭐가 있음 & 최근 높이가 현재 높이보다 더 큼
        building += 1 # 건물 추가
        stack.pop() # 높이가 낮아졌다 -> 최근 높이의 건물이 끝남. 스택에서 제거.
    if stack and stack[-1] == y: # 스택에 뭐가 있음 & 최근높이 = 현재 높이
        continue # 중복이니 스택에 넣을 필요 없음.
    stack.append(y) # 스택에 아무것도 없거나 현재 높이가 더 큰 경우 스택에 추가 

# 남은 건물은 더해주기. 
# 마지막 건물의 경우 비교할수있는 높이가 없어서 체크되지 않았을수있음.
while stack: 
    if stack[-1] > 0:
        building += 1
    stack.pop()

print(building)

 

 

 

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