[백준 22866] 탑 보기 (C++)

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

22866번: 탑 보기

문제

---

일직선으로 다양한 높이의 건물이 총 N개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

 i번째 건물 기준으로 i - 1, i - 2, ..., 1번째 건물은 왼쪽에, i + 1, i + 2, ..., N번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 L이라고 가정하면 높이가 L보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다.

번호	1	2	3	4	5	6	7	8
높이	3	7	1	6	3	5	1	7
보이는 건물 번호	2	x	2, 4, 8	2, 8	2,4,6,8	2,4,8	2,4,6,8	x

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

---

첫번째 줄에 건물의 개수 N이 주어진다.

두번째 줄에는 N개의 건물 높이가 공백으로 구분되어 주어진다.

출력

---

 i(1 ≤  i ≤ N)번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 i번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

 

문제 풀이

---

 오큰수의 응용.

오른쪽에서부터 왼쪽 끝까지 스택에 있는 index에 해당하는 빌딩의 높이와 비교한 후 i값을 저장해준다.

i번째 빌딩보다 스택의 top()에 해당하는 index의 빌딩 높이가 더 크다면 그 빌딩은 볼 수 있으므로 가장 가까운 빌딩의 번호를 저장하는 배열을 업데이트해준다. 스택에는 top index 빌딩보다 더 높은 빌딩들만 저장되어있을 것이므로, i번째 빌딩에서 스택에 있는 빌딩들을 볼 수 있다. 즉, 스택의 현재 원소 개수가 i번째 빌딩에서 볼 수 있는 빌딩의 개수이다.

i번째 빌딩보다 스택의 top에 해당하는 index의 빌딩 높이가 작거나 같다면 pop해주면서 빌딩 높이가 큰 것을 찾는다.

왼쪽에서부터 오른쪽 끝까지 같은 방법으로 i번째 빌딩 기준으로 왼쪽에 있는 빌딩 중 볼 수 있는 것을 찾는다.

 

아래 접은 글은 입력 예제 1의 3 7 1 6 3 5 1 7을 예시로 들었다.

먼저 오른쪽에서부터 왼쪽 끝까지 스택에 넣으며 탐색해본다.

8(idx 7)번째 빌딩은 맨 오른쪽이므로 8번째 빌딩의 오른쪽 빌딩에서 큰 건물은 없다.  탐색 후 스택에 index인 7을 넣는다. 가장 가까운 오른쪽 빌딩은 없다.

스택

(top) 7

near Building	MAX	MAX	MAX	MAX	MAX	MAX	MAX	MAX
canSee Building Count	0	0	0	0	0	0	0	0

 

7(idx 6)번째 빌딩의 높이와 스택의 top index 빌딩의 높이를 반복해서 비교한다. 1보다 index 7 빌딩 높이인 8이 더 크므로 index 7 건물을 볼 수 있다. 해당 건물이 가장 가까운 건물의 번호이므로 nearBuilding을 업데이트 하고, 스택에 있는 원소의 개수가 7번째 빌딩에서 볼 수 있는 오른쪽 빌딩의 개수이다. 탐색 후 스택에 index인 6을 넣는다.

스택

(top) 6 7

near Building	MAX	MAX	MAX	MAX	MAX	MAX	7	MAX
canSee Building Count	0	0	0	0	0	0	1	0

 

6(idx 5)번째 빌딩의 높이와 스택의 top index 빌딩의 높이를 반복해서 비교한다. 5보다 index 6 빌딩 높이인 1이 더 작으므로 pop()한다. 5보다 top index 7 빌딩 높이인 8이 더 크므로 index 7 건물을 볼 수 있다. 해당 건물이 가장 가까운 건물의 번호이다. 탐색 후 스택에 index인 5를 넣는다.

스택

(top) 5 7

near Building	MAX	MAX	MAX	MAX	MAX	7	7	MAX
canSee Building Count	0	0	0	0	0	1	1	0

 

5(idx 4)번째 빌딩의 높이와 스택의 top index 빌딩의 높이를 반복해서 비교한다. 3보다 index 5 빌딩 높이인 5가 더 크므로 해당 건물을 볼 수 있다. 이 건물이 가장 가까운 건물의 번호이며, 스택에 저장된 2개의 index 빌딩이 볼 수 있는 건물의 수이다. 탐색 후 스택에 index인 4를 넣는다.

스택	(top) 4 5 7

near Building	MAX	MAX	MAX	MAX	5	7	7	MAX
canSee Building Count	0	0	0	0	2	1	1	0

 

4번째 빌딩(idx 3): 같은 방식으로 탐색하면 스택에서 4, 5가 pop()되고 7만 남는다. 탐색 후 index 3을 넣는다.

스택

(top) 3 7

near Building	MAX	MAX	MAX	7	5	7	7	MAX
canSee Building Count	0	0	0	1	2	1	1	0

 

3번째 빌딩(idx 2): 스택의 top index 빌딩이 더 높다. index 2가 들어간다.

스택	(top) 2 3 7

near Building	MAX	MAX	3	7	5	7	7	MAX
canSee Building Count	0	0	2	1	2	1	1	0

 

2번째 빌딩 (idx 1): 스택에서 2, 3, 7모두 pop()된다. index 1이 들어간다.

스택

(top) 1

near Building	MAX	MAX	3	7	5	7	7	MAX
canSee Building Count	0	0	2	1	2	1	1	0

 

1번째 빌딩 (idx 0): 스택의 top index 빌딩이 더 높다.

near Building	1	MAX	3	7	5	7	7	MAX
canSee Building Count	1	0	2	1	2	1	1	0

 

같은 방식으로 왼쪽-> 오른쪽 탐색을 진행하며 nearBuilding과 canSeeBuildingCount을 업데이트 한다.

아래는 코드.

#include <iostream>
#include <stack>
#include <utility>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	stack<int> s;
	cin >> N;
	int* buildings = new int[N];
	int* nearBuilding = new int[N];
	int* canSeeBuildingCount = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> buildings[i];
		nearBuilding[i] = 1000000;
		canSeeBuildingCount[i] = 0;
	}
	for (int i = N - 1; i >= 0; i--)
	{
		if (s.empty())
		{
			s.push(i);
		}
		else
		{
			while (!s.empty())
			{
				if (buildings[i] < buildings[s.top()])
				{
					nearBuilding[i] = s.top();
					canSeeBuildingCount[i] = s.size();
					break;
				}
				else
				{
					s.pop();
				}
			}
			s.push(i);
		}
	}
	while (!s.empty())
	{
		s.pop();
	}
	for (int i = 0; i < N; i++)
	{
		if (s.empty())
		{
			s.push(i);
		}
		else
		{
			while (!s.empty())
			{
				if (buildings[i] < buildings[s.top()])
				{
					if (abs(nearBuilding[i]- i ) >= abs(s.top() - i))
					{
						nearBuilding[i] = s.top();
					}
					canSeeBuildingCount[i] += s.size();
					break;
				}
				else
				{
					s.pop();
				}
			}
			s.push(i);
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << canSeeBuildingCount[i];
		if (canSeeBuildingCount[i] != 0)
		{
			cout << " " << nearBuilding[i] + 1;
		}	
		cout << "\n";
	}
	return 0;
}