BOJ 1863 - 스카이라인 쉬운거

문제 링크

문제#

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

입력#

첫째 줄에 n이 주어진다. (1 <= n <= 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 <= x <= 1,000,000. 0 <= y <= 500,000) 첫 번째 지점의 x좌표는 항상 1이다.

출력#

첫 줄에 최소 건물 개수를 출력한다.

풀이#

문제 자체는 스택으로 해결하는 전형적인 유형이지만, 조건을 조금 꼼꼼히 봐야 한다.

왼쪽에서 오른쪽으로 보면서 현재 유지 중인 건물 높이들을 스택에 넣어 관리한다. 새로 들어온 높이 y가 스택 top보다 작아지면 그보다 큰 높이들은 여기서 끝난 것이므로 pop 하면서 건물 개수를 증가시킨다.

주의할 점은 두 가지다.

1. 새 높이가 스택 top과 같다면 같은 높이의 건물이 이어지는 상황이므로 중복으로 세면 안 된다.
2. 새 높이가 0이라면 건물이 없는 구간을 뜻하므로 스택에 넣지 않아야 한다.

즉, 높이가 내려갈 때만 pop 하며 개수를 세고, 같은 높이는 무시하고, 0은 push 하지 않으면 된다. 모든 입력을 처리한 뒤 스택에 남아 있는 높이들도 아직 끝나지 않은 건물이므로 그 개수를 답에 더해 주면 최소 건물 수를 구할 수 있다.

코드#

#include <iostream>
#include <stack>
using namespace std;
 
int n;
stack<int> s;
 
int solve() {
	int ans = 0;
	while (n--) {
		int x, y;
		cin >> x >> y;
 
		while (!s.empty() && y < s.top()) {
			s.pop();
			ans++;
		}
 
		if (!s.empty() && y == s.top()) continue;
 
		if (y > 0)	s.push(y);
	}
 
	
	ans += s.size();
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
    cin >> n;
 
    cout << solve() << '\n';
}

복잡도#

• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(n)$

마무리#

스택 문제답게 구현은 짧지만, 같은 높이와 0 처리 조건을 빼먹으면 답이 쉽게 틀어진다. 핵심은 “언제 건물이 끝났다고 볼 것인가”를 스택의 pop 시점으로 정확히 잡는 데 있다.