[백준] #17298: 오큰수

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

17298번: 오큰수

 

문제 설명

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

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

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

코드 (1)

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    
    int k;
    int arr[k];
    stack<int> st;
    
    //입력
    cin>>k;
    for(int i=0; i<k; i++){
        cin>>arr[i];
    }
    
    for(int i=k-1; i>=0; i--){
        if(i==k-1){ //마지막 원소일때
            st.push(-1);
        }
        else{
            for(int j=i+1; j<k; j++){ 
                if(arr[i]<arr[j]){
                    st.push(arr[j]);
                    break;
                }
                if(j==k-1){ //오른쪽에 있는 수가 모두 작다면
                    if(arr[i]>arr[j]) st.push(-1);
                }
            }
        }
    }
    
    //출력
    while(k--){
        cout<<st.top()<<" ";
        st.pop();
    }
    
    return 0;
}

코드(2)

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    int k;
    int arr[1000001]={0},ans[1000001]={0};
    stack<int> st;
    
    //입력
    cin>>k;
    for(int i=0; i<k; i++){
        cin>>arr[i];
    }
    
    for(int i=k-1; i>=0; i--){
        while(!st.empty() && arr[i]>=st.top()) st.pop();
        
        if(st.empty()) ans[i]=-1;
        else ans[i]=st.top();
        
        st.push(arr[i]);
    }
    
    //출력
    for(int i=0; i<k; i++){
        cout<<ans[i]<<" ";
    }
}

---

처음에는 코드(1)의 방법으로 문제를 풀었고, 런타임에러 때문에 코드(2)의 방법으로 문제를 풀었다

코드(1)

우선 입력하는 수를 배열에 담고,
이중 반복문을 이용해서 오른쪽에 있는 큰 수 중 가장 왼쪽에 있는 수를 스택에 담았다.
배열의 첫번째 원소부터 반복문을 돌리면 나중에 스택을 출력할때 역순으로 출력이 되기 때문에
배열의 마지막 원소부터 반복문을 돌렸다

i) 만일 배열의 마지막원소라면 -1을 스택에 넣고
ii) 오른쪽에 있는 수 중 큰 수가 있다면 그 수를 스택에 넣는다
iii) 반대로 오른쪽에 있는 수 중 큰수가 없다면 스택에 -1을 넣는다

이렇게 코드를 돌렸을때 결과값은 알맞게 나온다
하지만 백준에 제출했을 때는 계속해서 런타임에러가 발생했다 ( 아직 이유는 찾지 못했다.. 도대체 왜일까)

코드(2)

코드(2)도 마찬가지로 입력하는 수를 배열에 담는다.
하지만 코드(2)는 코드(1)과 다르게 입력하는 수를 스택에도 담아 비교를 하고, 오른쪽에 있는 큰 수는 배열에 담는다

i) 입력한 수를 arr 배열에 담는다
ii) 반복문을 arr의 마지막 원소부터 돌린다
    ii-a) 스택 st가 비어있지 않고, 비교하는 arr 원소가 st.top 보다 크면 st.top 을 삭제한다
    ii-b) 스택이 비어있으면, 오큰수를 담는 배열 ans에 -1을 넣는다
    ii-c) 스택이 비어있지 않으면, ans에 st.top()을 담는다
    ii-d) 스택에 비교하는 arr 원소를 담는다

이해하기 쉽게 예를 들어보자

5 3 2 7 이라는 배열이 있다고 가정하면

첫번째로 비교할 원소는 7이다. 이때 7은 처음 비교하는 원소이므로 스택은 비어있는 상태이다.
스택이 비어있기 때문에 ans[3]= -1 이된다.
그리고 7을 스택에 넣어준다

두번째로 2를 비교해보자. 현재 st.top의 값은 7이다.
스택이 비어있지 않고, 2(arr)가 7(st.top)보다 작기 때문에 st.top을 삭제하지 않는다. 그리고 ans 에 현재 st.top인 7을 넣어준다.
마지막으로 2를 스택에 넣어준다

세번째로 3을 비교해보자. 현재 st.top은 2이다.
스택이 비어있지 않고, 3(arr)이 2(st.top)보다 크기때문에 st.top을 삭제해준다. 그러면 st.top이 7로 바뀐다.
그렇다면 3(arr)이 7(st.top)보다 작기때문에 st.top은 삭제하지 않고, ans에 현재 st.top인 7을 넣어준다.
마지막으로 3을 스택에 넣어준다

이 과정을 반복하면 최종적으로 ans에는 오큰수가 담기게 되고, 오큰수를 출력해주면된다.

---

** 코드 (1) 에서 런타임에러 발생한 이유

같은 수를 넣었을 때 경우 처리를 해주지 못했다.