[백준][C++] 17298: 오큰수

 

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

17298번: 오큰수

 

 

 

 

 

---

- 문제

 

  A1, A2, ..., An으로 이루어진 A배열이 있을 때 Ai에 대해서 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 출력하는 문제다.

 

 

---

- 해설

(틀린 방법)

 

Ai에서부터 그 이후에 있는 숫자 중에서 자신보다 크면서 가장 근접한 숫자를 출력하면 되는 문제인 줄 알고 풀었다.

 

백준 기준으로 대략 50%까지는 천천히 되다가 시간초과가 나버린다.

 

심한 경우에는 O(n^2)이 되기 때문에 그런 거 같다.

 

 

 

(맞는 방법)

 

https://cocoon1787.tistory.com/347

 

위에 다른 사람 블로그 글이 있는데, 저는 여기서 보고 이해했습니다.

 

그림으로 너무 설명을 잘 해 주셔서 이해하기가 좋았어요.

 

 

이해를 하게 되면 만드는 건 쉽지가 않은데, 혼자서 저런 방식으로 풀어야 겠다고 생각을 하는게 어려운 것 같습니다.

 

 

 

 

---

- 풀이

 

틀린 풀이

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


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, temp, now;
    bool isNGEd = false;
    vector<int> A;
    A.reserve(1000001);
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> temp;
        A.push_back(temp);
    }
    for(int i = 0; i < N; i++){
        now = A[i];
        isNGEd = false;
        for(int j = i + 1; j < N; j++){
            if(A[j] > now){
                cout << A[j] << ' ';
                isNGEd = true;
                break;
            }
        }
        if(!isNGEd){
            cout << "-1 ";
        }
    }
    
    
    
    return 0;
}

 

 

맞은 풀이

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


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    stack<int> st;
    int A[1000001];
    int answer[1000001];
    
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int i = N-1; i >= 0; i--){
        while(true){
            if(st.empty()){
                st.push(A[i]);
                answer[i] = -1;
                break;
            }
            else if(st.top() > A[i]){
                answer[i] = st.top();
                st.push(A[i]);
                break;
            }
            else{
                st.pop();
            }
        }
    }
    for(int i = 0; i < N; i++){
        cout << answer[i] << ' ';
    }
    
    
    return 0;
}

 

 

---

- 새롭게 알게 된 점