백준

백준 17298 오큰수

콩순이냉장고 2022. 3. 20. 23:01

문제 URL : https://www.acmicpc.net/problem/17298

 

17298번: 오큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

문제 접근법 : 스택을 이용하는문제인데

매 입력받는 수를 스택에 쌓습니다. 물론 현재 인덱스와함께

근데 스택에 쌓기전 현재 입력받은수가 스택에 쌓여있는 수보다 크다면 전부 꺼내어 스택에 있는 인덱스에 있는 수에 입력받은 수를 저장하면 되기때문에 크게 어렵지 않은 문제입니다.

 

소스코드 : 

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
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int n;
void input() {
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
}
void solve() {
    stack<pair<int, int>> st;
    vector<int> idx(n, -1);
    st.push({ v[0],0 });
    for (int i = 1; i < n; i++) {
        while (!st.empty() && st.top().first < v[i]) {
            idx[st.top().second] = v[i];
            st.pop();
        }
        st.push({ v[i],i });
    }
    for (int i = 0; i < n; i++)
        cout << idx[i] << " ";
    cout << "\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    input();
    solve();
}
 cs

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.