[C++] BOJ(백준) 1863 스카이라인 쉬운거

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

1863번: 스카이라인 쉬운거

 

스택 자료구조 문제다.

 

이 문제를 볼 때마다 뭘 구하라는 건지 이해가 안돼서 패스했었는데 드디어 이해하고 해결했다.

스카이라인의 높이가 바뀌는 경우 좌표가 주어진다.

모든 칸을 커버하는 최대의 직사각형 개수를 구하는 문제라고 판단했다.

 

스택 문제긴 하지만 스택을 이용하지 않았다.

높이가 바뀌는 지점이 순서대로 입력되므로 입력받는 대로 결과를 처리했다.

 

이전보다 높아졌는지 낮아졌는지를 확인하기 위해 이전 값을 저장하는 변수를 만들고 초기값은 0으로 뒀다.

스카이라인의 높이가 2 3 2 라면 높낮이 변화는 두 번 있지만 2는 쭉 이어져 하나의 직사각형을 만들 수 있다.

이 부분을 판단하기 위해 이전 값 중 나온 적이 있는지 확인하는 배열을 만들었다.

 

이 배열은 현재 입력된 값이 이전 값보다 크다면 현재 값에 대해 배열을 true로 바꾸고 res 값을 1 더해준다.

작다면 우선 현재 값의 배열이 false인지, 0이 아닌지 확인하고 두 조건에 모두 부합한다면 res 값을 1 더해준다.

그리고, 이전에 나온 값들 중 현재 높이보다 큰 높이들에 대해 배열 값을 false로 바꾼 후

위와 동일하게 현재 값에 대해 배열을 true로 바꾼다.

 

이전 값을 현재 값으로 갱신한다.

#include <iostream>
using namespace std;

int n, res, ma;
bool arr[500001];

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	int tmp = 0;
	for (int i = 0; i < n; i++) {
		int a, b;	cin >> a >> b;
		ma = max(ma, b);

		if (b > tmp) {
			res++;
			arr[b] = true;
		}
		else {
			if (!arr[b] && b != 0) res++;
			for (int j = b; j <= ma; j++) arr[j] = false;
			arr[b] = true;
			ma = b;
		}
		tmp = b;
	}
	cout << res;
}

시간 복잡도를 계산해보기 전에 매번 500000만큼 반복되는 경우가 있다면 시간초과가 나지 않을까 했는데 아니었다.

항상 500000만큼 돌리지 않고 지금까지 나온 값의 최댓값까지만 반복하면 시간을 줄일 수 있지 않을까 싶어 시도했다.

입력 받을 때마다 ma의 값을 b와 비교해서 최댓값을 저장했다.

그러나 중간에 현재 값 이후의 인덱스 값을 초기화 하는 경우가 있기 때문에 시간을 좀 더 줄일 수 있을 것 같았다.

그래서 추가한 부분이 else 부분의 ma = b다.

시간이 반으로 줄었다.

 

1트 (500000)

2트 (최댓값)

3트 (현재의 최댓값)