알고리즘 :: 백준 :: 17298 - 오큰수

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)

✏️ 문제풀이

3 5 2 7

예제 입력 1을 먼저 생각해봅시다.

• 3은 5와 짝지어집니다.
• 5는 7과 짝지어집니다.
• 2는 7과 짝지어집니다.
• 그래서 결과적으로 `5 7 7 -1` 이라는 답이 나옵니다.

짝 지어짐, 짝을 찾음 이라는 개념에서 '스택'을 떠올리셔야 합니다. (관련문제: 9012 :: 괄호, 4949 :: 균형잡힌 세상)

1. 스택의 가장 위에 있는 값 (`top()`)보다 작은 값을 만나면 스택에 `push()` 됩니다.
2. 반면에 더 큰 값(`big` 이라고 할까요?)을 만나면 `big`보다 큰 값이 스택의 가장 위에 올 때까지 `pop()` 합니다. (없다면 스택이 비게 되겠지요)
3. `pop()` 하면서 오큰수를 저장한 배열에 오큰수를 저장합니다. `오큰수[스택.top()] = big;`

📝 코드

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

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int N;
	cin >> N;
	
	stack<int> stk;
	vector<int> arr(N), ret(N, -1);
	
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
		// 1. 오큰수를 발견, 스택에 있는것들 쏟으면서 오큰수 지정
		while (!stk.empty() && arr[stk.top()] < arr[i]) {
			ret[stk.top()] = arr[i];
			stk.pop();
		}
		// 2. 다음 오큰수를 발견할 때까지 스택에 담기
		stk.push(i);
	}
	for (int i = 0; i < N; ++i) cout << ret[i] << ' ';
}

 

🔗 코드 링크

🕧 결과