백준17298 오큰수, 백준17299 오등큰수

작성일 | In

문제 링크

  • http://icpc.me/17298
  • http://icpc.me/17299

사용 알고리즘

  • Stack

시간복잡도

  • O(N)

풀이

17298 오큰수

monotone stack을 잘 사용해주면 됩니다.
배열의 맨 뒤부터 스택에 넣고, 스택을 항상 순감소상태를 유지시켜봅시다.
손으로 그려서 계산을 해보면 스택의 맨 위에 있는 원소가 Ai의 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수가 됩니다.

-1을 처리해주는 것은 처음에 스택에 inf를 넣어주면 됩니다.

17299 오등큰수

기본적인 아이디어는 17298번과 같습니다. 다만 스택을 감소상태로 유지할 때 원소끼리 비교하는 것이 아닌 f함수값끼리 비교해야 합니다.

전체 코드

17298 오큰수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int> v(n), ans(n);
	for(int i=0; i<n; i++) cin >> v[i];

	stack<int> stk; stk.push(1e9+7);
	for(int i=n-1; i>=0; i--){
		while(stk.top() <= v[i]) stk.pop();
		if(stk.top() >= 1e9) ans[i] = -1;
		else ans[i] = stk.top();
		stk.push(v[i]);
	}
	for(auto i : ans) cout << i << " ";
}

17299 오등큰수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

int cnt[1010101];
vector<int> v, ans;
stack<int> stk;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	v.resize(n); ans.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
		cnt[v[i]]++;
	}
	cnt[0] = 1e9+7;

	stk.push(0);
	for(int i=n-1; i>=0; i--){
		while(cnt[stk.top()] <= cnt[v[i]]) stk.pop();
		if(cnt[stk.top()] > 1e9) ans[i] = -1;
		else ans[i] = stk.top();
		stk.push(v[i]);
	}
	for(auto i : ans) cout << i << " ";
}