[백준 1863번] 스카이라인 - python

문제

백준 1863번 스카이라인

현재 진행하고 있는 99클럽 코테 스터디에서 코테 모의고사를 진행해 푼 문제이다.
문제 이해하기가 어려웠는데, 다른 분의 설명을 듣고 이해를 했다.

아래 블로그에 건물 사진을 참고하면 더 이해가 잘 간다.
사진 참고

풀이

좌표 x, y가 주어지면 y가 건물의 높이값이고 다음 입력받는 값이 전의 값보다 크면 새로운 건물이 있다는 의미로 건물 수를 더해주면 된다.

import sys
input = sys.stdin.readline

n = int(input())
skylines = []
stack = [0]
cnt = 0

for _ in range(n):
    skylines.append(list(map(int, input().split()))[1]) # 높이값만 저장

def isHigher(h):
    global cnt
    if stack[-1] < h: # 새로운 건물이면 건물 수 세주고, stack에 추가
        cnt += 1
        stack.append(h)
        return True
    else: return False

for h in skylines:
    if isHigher(h) == False:
        while stack[-1] > h: # 그렇지 않으면 stack.pop()
            stack.pop()

        isHigher(h)

print(cnt)

비교값 = stack[-1]

비교값보다 다음 높이 값(h)이 더 크면 stack에 넣어주고 건물 수를 +1 해주고,
더 작다면 h가 더 커질 때까지(건물 수가 늘어나는 경우까지) stack.pop으로 원소를 빼주면 된다.

⏰ 시간복잡도 O(n)
최악의 경우 stack의 모든 요소를 확인하므로 O(n)