기타:: 1104 일기

백준 풀이 - 스택 연습문제

문제리뷰

2493 탑 : 감지할 탑만 스택에 넣어놓는 방식 (현재 탑보다 키가 큰 탑만 감지하면 되기 때문)

6198 옥상 정원 꾸미기 : 관점을 관찰 당하는 빌딩을 기준으로 스택 구성

(스택에 있는 빌딩은 나를 관찰할 수 있는 빌딩이다)

 

2493 탑

초기 코드 (시간초과)

스택 2개를 써서 pop한 값을 S2에서 넣은 다음 S1에 다시 넣어주어서 모든 경우를 판단하는 코드 

n이 최대 500,000이기 때문에 O(N^2)의 코드을 짜면 시간 초과가 발생한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	int tmp;
	stack<int> S1;
	stack<int> S2;
	while(n--) {
		cin >> tmp;
		S1.push(tmp);
	}
	
	stack<int> result;
	while(S1.size()) {
		tmp = S1.top();
		S1.pop();

		while(S1.size() && S1.top() < tmp) {
				S2.push(S1.top());
				S1.pop();
			}
		result.push(S1.size());
		
		while(S2.size()) {
			S1.push(S2.top());
			S2.pop();
		}
	}
	
	while(result.size()) {
		cout << result.top() << ' ';
		result.pop();
	}
}

 

수정 코드

감지할 탑만 스택에 넣어놓는 방식 (현재 탑보다 키가 큰 탑만 감지하면 되기 때문)

#include <bits/stdc++.h>
using namespace std;

int nums[500000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	stack<pair<int, int>> S;
	for(int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	
	int cur;
	for(int i = 0; i < n; i++) {
		cur = nums[i];
		
		while(S.size() && S.top().second < cur)
			S.pop();

		if(S.empty()) cout << "0 ";
		else cout << S.top().first << " ";
		
		S.push({i + 1, cur});
	}
}

 

6198 옥상 정원 꾸미기

monotone stack

스택의 원소들을 오름차순, 내림차순 상태로 유지하도록 함

https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/

monotone stack