[백준] 1863 스카이라인 쉬운거 python

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

1863번: 스카이라인 쉬운거

제목에 쉬운거라고 써있는데 생각하기 조금 어려웠다. N의 최대값이 50000이어서 입력값을 받으면서 한번에 찾아야한다는 생각이 들어서 머리가 잘 돌아가지 않았나보다. (힌트를 봐서 다행히 빨리 풀수 있었다)

알고리즘은 스택을 사용해서 항상 오름차순이 되도록 만들고, 현재 입력값(건물의 높이)와 이전 건물의 높이를 비교해서 풀면된다. 

이렇게만 말하면 무슨 말인지 잘 모를수 있으므로 풀어서 정리해보면 다음과 같다.

1) 현재 높이(cur_h)가 이전 빌딩의 높이(building[-1])보다 큰 경우 push

2) 현재 높이가 이전 빌딩의 높이보다 작은 경우(같은 경우는 입력 케이스에서 제거된다)

2-1) 이전 빌딩 높이가 같거나 커질때까지 pop 반복

2-2) 반복문이 끝나고 이전 빌딩 높이보다 크다면 push
(높이가 같은 경우는 앞에서 이미 체크했으므로 넘어가도된다)

 

push할 때 건물이 하나씩 추가되므로 이때 빌딩 개수도 하나씩 더해주면 최소 빌딩 갯수가 나오게 된다.

 

 

 

import sys; input = sys.stdin.readline

def main():
    N = int(input())
    building = [0]
    answer = 0
    for _ in range(N):
        x, cur_h = map(int, input().split())

        if cur_h > building[-1]:
            answer += 1
            building.append(cur_h)
        else: # cur_h < building[-1]
            while building[-1] > cur_h:
                building.pop()

            if building[-1] < cur_h:
                answer += 1
                building.append(cur_h)
    print(answer)


if __name__ == '__main__':
    main()