[17298] 오큰수 - 스택/monotone stack ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/17298

17298번: 오큰수

---

[ 문제 접근 ]

 

옥상 정원 꾸미기와 마찬가지로 monotone stack 을 이용해야하는 문제.

 

monotone stack 을 이용한 문제를 여러개 풀고 있다.   O ( N ) 시간 복잡도

 

문제는 문제 분류가 stack 이라는걸 아니깐 stack을 이용해서 푸는거지,

코딩 테스트를 할때, 이 문제를 맞딱드리면 바로 stack 이 나올까 싶다..

 

무튼, 이 문제는 N의 크기가 최대 1,000,000 이여서 이중 for문으로 하나씩 검사하는 O(N^2) 의 풀이로는 어림도 없다.

 

 

 

 

---

[ 최종 코드 ]

 

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

using std::cout; using std::cin;
using std::vector;

int n;
int result[1000001];

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	std::stack<std::pair<int, int>> st;
	cin >> n;

	int cnt = 0;
	std::fill_n(result + 1, n, -1);  // result 배열 -1 로 초기화

	int size = n;

	while (n--) {
		int a;
		cin >> a;
		cnt++;
		
        // 오큰수 찾음.
		while (!st.empty() && st.top().first < a) {
			result[st.top().second] = a;
			st.pop();
		}

		st.push({ a,cnt });
	}
	// 스택에 남아있는 값은 오큰수가 없는 값. 고로 그대로 -1 출력.
	for (int i = 1; i <= size; i++) {
		cout << result[i] << " ";
	}

	return 0;
}

---

[ Key Point ]

 

 

👉 입력으로 주어진 수열을 한번에 받고 문제를 풀어도 되는데, 스택 문제는 보통 이런식으로 입력 받을때마다 로직을 처리해주는게 많이 보여서 위와 같이 풀어 봤다.

다만 인덱스를 찾을 수 없었는데, cnt 를 두어  cin 돌때 마다 +1 해주면서 인덱스로 사용했다.

 

👉 while (!st.empty() && st.top().first < a )     <-------   부등호 방향을 <= 이렇게 하면 틀린다. 조심하자

---

[ 다른 사람 풀이 ]

 

ref :: https://it-and-life.tistory.com/252