[BOJ-2493] 탑 (C++)

백준 2493 탑

 

2493번: 탑

 

문제 설명

 

 - 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 세운다.

 

 - 각 탑의 꼭대기에는 레이저 송신기를 설치했다.

 

 - 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사한다.

 

 - 탑의 기둥에는 레이저 신호를 수신하는 장치가 설치되어 있다.

 

 - 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

 

 - 탑들의 개수 N과, 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는 구하라.

   ( 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다. )

---

 

입력 값

 

 - 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다.

   ( 1 <= N <= 500,000 )

 

 - 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 수선대로 하나의 빈칸을 사이에 두고 주어진다.

   ( 1 <= 탑의 높이 <= 100,000,000 )

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 특정 위치의 탑의 레이저를 수신하는 탑은 해당 탑보다 오른쪽에 있는 탑 중 가장 가까운 탑이다.

 

 - 간단한게 생각하면, 오른쪽부터 탐색을 시작하여, 해당 탑의 위치부터 왼쪽으로 탐색하여

   해당 탑 보다 큰 탑이 나오면 해당 인덱스를 저장하면 된다.

 

 - 이 방법의 경우 최악의 경우는 왼쪽부터 오름차순으로 탑의 위치가 되어 있는 경우이다.

   이 경우 가장 오른쪽 탑은 N-1번 탐색, 그 왼쪽 탑은 N-2번 ... 마지막 탑 전 탑은 1번, 마지막 탑은 0번 탐색한다.

   즉, 시간 복잡도는 O(N-1 + N-2 + N-3 + ... + 1 + ) = O($N^2$) 이 된다.

 

 - N의 최댓값이 50만이기 때문에 O($N^2$)은 불가능하다.

 

 - 이 문제를 잘 살펴보면, 해당 탑을 수신하는 탑으로 결정되는 것은 해당 탑의 높이가 처음으로 다른 탑 보다 큰 경우이다.

 

 - 위 그림에서 화살표가 위치한 탑을 수신하는 탑으로 결정하는 탑은 파란색 탑들이다.

 

 - 주황색 탑의 경우 해당 탑 왼쪽의 탑이 이미 레이저를 수신하기 때문에 해당되지 않는다.

 

 - 그렇다면, 해당 탑을 수신하는 탑으로 결정하는 탑을 찾는 방법은 무엇일까?

 

 - 그것은 해당 탑(초록색 탑)의 오른쪽부터 탐색하면서 살펴보면 된다.

   초록색 탑 보다 작으면서, 왼쪽에 해당 탑 보다 큰 탑이 나오지 않은 경우가 된다. 

 

 - 이 방법을 쉽게 구현하는 방법은 스택을 이용하는 것이다.

 

 - 오른쪽부터 탐색을 시작하면서, 현재 인덱스의 탑 높이와 스택에 들어있는 탑의 높이를 비교한다.

   인덱스 탑의 높이 > 스택 탑의 높이 인 경우 스택 탑의 레이저를 인덱스 탑이 수신한다는 것이다.

   인덱스 탑의 높이 < 스택 탑의 높이 인 경우 스택 탑의 레이저를 인덱스 탑이 수신하지 못한다는 것이다.

   또한, 스택 탑 오른쪽에 있는 탑들은 레이저는 당연히 수신이 불가능해진다.(스택 탑이 모든 레이저를 수신하기 때문에)

 

 - 이 과정을 그림으로 설명하면 다음과 같다.

해당 인덱스와 비교할 스택의 값이 없기 떄문에 스택에 5를 넣는다..

 

 

인덱스 높이(11) > 스택 top 높이(5) 이기 때문에 스택 pop을 하고, 높이 5의 탑은 높이 11 탑이 수신함을 저장한다.

 

인덱스 높이(10) < 스택 top 높이(11) 이기 스택에 10을 넣는다.

 

인덱스 높이(8) < 스택 top 높이(10) 이기 스택에 8을 넣는다.

인덱스 높이(3) < 스택 top 높이(8) 이기 스택에 3을 넣는다.

인덱스 높이(12) > 스택 top 높이(3) 이기 때문에 스택의 top을  pop하고, 높이 3의 탑은 높이 12 탑이 수신함을 저장한다.

 

위 과정을 스택에 있는 top들이 인덱스 높이보다 작다면 모두 반복하게 된다.

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int height[500001];
int result[500001];

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

	int N,h;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> h;
		height[i] = h;
	}

	// 인덱스
	stack<int> st;

	for (int i = N - 1; i >= 0; i--) {

		while (!st.empty()) {

			if (height[i] < height[st.top()]) {
				break;
			}

			result[st.top()] = i+1;
			st.pop();

		}

		st.push(i);

	}

	for (int i = 0; i < N; i++) {
		cout << result[i] << " ";
	}
	cout << endl;

	return 0;
}