백준 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)