[백준] 2493번 탑

www.acmicpc.net/problem/2493

2493번: 탑

 

이제는 방식을 외우긴 했는데 코드짜면서 깊게 생각하다보니 또 헷갈려서 포스팅한다.

언제쯤 익숙하게 외우려나... 휴...

 

stack을 써야하는 이유

모든 탑에 대해서 높이를 입력받은 i번째의 탑을 기준으로 앞쪽으로 이동하며 더 높은 탑을 찾아도 되지만,

O(N^2)의 시간복잡도를 가지게 된다.

하지만 이를 stack을 통해 구현할 경우, 탐색의 경우의 수를 비약적으로 줄여 시간에서 큰 이득을 볼 수 있다.

 

변수

stack s - pair를 통해 (벽의높이, 벽의번호) 입력

vector result - i번째 벽의 신호가 몇번째 벽에 부딪히는지에 대한 정보를 저장

 

알고리즘 방식

1. i번째 벽이 들어왔을 때, i번째 앞에 있는 벽들 중 i번째 벽보다 높이가 낮은 벽은 후에 신호를 수신할 수 없다.

   따라서 i번째 벽보다 낮은 벽은 s.pop()을 통해 제거해준다.

2.  i번째 벽보다 앞에 벽이 없었거나 벽이 없다면 s에 (벽의높이, 벽의번호)를 push, result에 0을 push

2-2 i번째 벽보다 높은 벽이 앞에 있다면 result에 (앞에 벽의 번호)를 push 후 s에 (i번째 벽의 높이, 벽의 번호)를 push

3. 1과 2를 N번 반복 후 result내부의 값을 순서대로 출력

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int N;
stack<pair<int, int>> s;
vector<int> result;

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

	

	cin >> N;

	int buf; // 탑의 높이 입력받는 버퍼
	int cnt = 1; //몇 번째 탑인지
	while (N--) {
		cin >> buf;
		if (s.empty()) { //앞에 벽이 없다면
			s.push({ buf, cnt++ });
			result.push_back(0); //s에 (벽의높이, 벽의 번호) 입력, result에 0 입력(신호 수신x)
		}
			

		else {           //앞에 벽이 있다면
			while (!s.empty() && s.top().first < buf) //s가 비거나 앞에 벽이 buf보다 작을 때
				/*s.empty() == 1이면 s.top()은 오류가 날 수 밖에 없지만 
				and 연산의 경우 앞에 0이 오면 뒷쪽 연산을 진행하지 않고 0 출력*/
				s.pop(); //높은 벽이 올 때까지 벽 제거 
			
			if (s.empty()) {  //buf보다 높은 벽이 앞에 없다면
				s.push({ buf, cnt++ });
				result.push_back(0); //s에 (벽의높이, 벽의 번호) 입력, result에 0 입력(신호 수신x)
			}
				
			else {           //buf보다 높은 벽이 앞에 있다면
				result.push_back(s.top().second);
				s.push({ buf, cnt++ }); //s에 (벽의높이, 벽의 번호) 입력, result에 (앞에 벽의 번호) 입력
			}				
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' '; //결과값 출력

}