문제 설명

이번 포스팅은 백준 21939번: 스카이라인 쉬운거 문제 풀이에 대한 기록입니다.

[ 입출력 ]

문제를 간단히 요약하자면, "스카이라인이 꺾이는 지점의 좌표들의 형태로 주어졌을 때, 이 스카이라인을 구성하는 최소 건물의 수를 알아내는 문제" 입니다.

조금 더 이해하기 쉽게 그림으로 설명해보겠습니다.

예제 입력을 그림으로 나타내면 위와 같은 스카이라인이 됩니다.

이 실루엣 안에 있을 수 있는 최소한의 건물은 다음과 같이 6개로 나눌 수 있게 됩니다.

풀이

1. 스카이라인이 낮아지는 지점에서 건물 수 더하기

---

이 문제를 푸는 방법은 생각보다 간단합니다.

스카이라인이 낮아지는 지점, 즉 "이전 점보다 $y$값이 작아지는 지점에서 건물을 세어주면" 됩니다.

스카이라인이 낮아졌다는 것은, 어떤 빌딩이 그 지점에서 끝났다는 의미로 생각할 수 있으므로 그때 건물을 카운트 해주면 되는 것입니다.

단, 한 가지 경우만 주의하면 됩니다.

예제에는 나와있지 않지만, c 지점에서처럼 "스카이라인이 낮아지며 한 번에 두 개 이상의 건물이 끝나는 경우"가 있을 수 있습니다.

이런 경우를 고려하여 알고리즘을 구현하면 됩니다.

2. 아이디어 구현하기

---

skylines = []
for i in range(n):
    skylines.append(int(sys.stdin.readline().split()[1]))
skylines.append(0)

먼저 스카이라인에서 고도가 변하는 지점들의 좌표를 저장해줍니다.

우리는 점들을 순서대로 보면서 $y$값만 비교하면 되기 때문에, 각 입력의 두 번째 값인 $y$값만 저장해줘도 됩니다.

마지막에 0을 추가해주는 이유는, 입력으로 스카이라인이 끝나면서 $y$가 0이 되는 점까지 주어지지 않기 때문에, 0을 추가해줌으로써 맨 마지막 건물까지 세어주기 위함입니다.

stk = [0]	# stack이 비지 않게 해주는 장치
for p in skylines:
    height = p
    while stk[-1] > p:
        if stk[-1] != height:
            answer += 1
            height = stk[-1]
        stk.pop()
    stk.append(p)   
print(answer)

이제 순서대로 점들을 보면서, 다음 과정을 반복합니다.

• stack의 top(이전에 나온 점)이 p보다 낮으면 바로 stack에 push

• stack의 top이 p보다 높으면 1개 이상의 건물이 끝났다는 의미이므로,

  • p와 비교하면서 끝난 건물을 하나씩 세어나가면서 pop

  • height의 역할 : 마지막으로 카운트한 건물의 높이를 기록해놓음으로써, 앞에서 이미 카운트한 건물을 또 카운트하지 않도록 방지함.
    ex) p가 (11, 0)일 때, (8, 1)이 카운트된 후 (5, 1), (1, 1)이 중복으로 카운트되지 않게 해줌

그리고 마지막에 카운트한 결과를 출력하면 됩니다.

문제 해결!

결과 코드

import sys

n = int(sys.stdin.readline())
answer = 0

skylines = []
for i in range(n):
    skylines.append(int(sys.stdin.readline().split()[1]))
skylines.append(0)

stk = [0]
for p in skylines:
    height = p
    while stk[-1] > p:
        if stk[-1] != height:
            answer += 1
            height = stk[-1]
        stk.pop()
    stk.append(p)   
print(answer)