[C++/BOJ] 백준 17298 오큰수(스택)

 

문제 : 

 

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

풀이방법 : 

2개의 벡터, 1개의 스택을 이용해 풀이하였습다.

 

 

0) n을 입력받고 v2라는 답을 저장할 벡터를 생성한다.

 

1) vector에 n개의 숫자를 입력받는다.

 

2) stack에 index를 넣는다.

 

3) stack에 있는 index값에 해당하는 vector값과 i값을 비교한다.

 

4)( i값은 stack에 있는 값보다 항상 오른쪽 값이므로) 큰 값을 v2벡터에 넣는다.

 

5) v2벡터를 출력한다.

 

 

코드 :

 

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

vector<int> v;
stack<int> stk;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v2(n + 1, -1);   // size는 n+1으로 , -1로 전부 초기화하면서 생성한다.
    for (int i = 0; i < n; i++) { 
        int num;
        cin >> num;
        v.push_back(num);
    }

    for (int i = 0; i < n; i++) {
        while (!stk.empty() && v[stk.top()] < v[i]) { // 스택이 비어있지않고 스택값보다 v[i]값이 크다면
            v2[stk.top()] = v[i]; // 큰값을 v2에 해당 인덱스 값에 저장
            stk.pop();  //큰값을 저장했으니 pop해준다.
        }
        stk.push(i); // 인덱스를 스택에 넣는다.
    }
    for (int i = 0; i < n; i++) { 
        cout << v2[i] << " ";
    }
}

 

 

while 부분이 약간 까다로웠습니다.

그리고 index를 넣는다는 생각과 2개의 벡터, 1개의 스택을 만들어 비교후 넣는다.

라는 것도 생각하기 힘들어 결국 답을 보고 풀었습니다.

 

이 문제를 풀었다면 탑도 풀어보시면 좋을것같습니다.

https://www.acmicpc.net/problem/2493

2493번: 탑

거의 똑같습니다.