이번 문제는 스택을 활용하여 해결하는 문제였다. 시간 제한을 보고 시간이 부족하겠다고 생각은 했지만 우선은 스스로 풀어보기로 했다.

• n만큼 반복하며 stack에 탑의 높이를 넣어준다.
• 이중 반복문 안에서 stack을 복사한다.
• 복사한 stack을 pop시키며 원래 stack의 top보다 크다면 그 때 해당하는 for문의 j값을 배열에 넣어주었다. (배열에는 인덱스 n에서 1로 가는 순서로 입력시켰다.)
• 완성된 크기 n의 배열을 인덱스 1부터 차례대로 출력해준다.

Code (TLE)

#include <iostream>
#include <stack>
#define MAX 500001
using namespace std;

int n;
int top;
stack<int> lazer;
int result[MAX];

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>top;
        lazer.push(top);
    }
}

void Solution(){
    for(int i=n-1; i>=0; i--){
        stack<int> test = lazer;
        int maxi=lazer.top();
        for(int j=i-1; j>=0; j--){
            test.pop();
            if(test.top()>=maxi){
                result[i]=j+1;
                break;
            }
        }
        lazer.pop();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    for(int i=0; i<n; i++){
        cout<<result[i]<<" ";
    }
    cout<<endl;
    return 0;
}

예상대로 시간초과라는 결과를 얻었다.

구글링을 통해 시간을 줄여 해결할 수 있는 코드를 참고하여 다시 작성하였다.

• 탑에 대한 배열을 만든다
• stack<pair< int >, < int >> 구조의 스택을 만든다. ( first는 인덱스, second는 높이를 담는다. )
• 탑의 높이보다 스택의 second가 더 크다면 스택의 first를 출력해준다.
• first를 출력했다면 반복문을 탈출한다.
• first를 출력하지 못했다면 스택을 pop해준다.
• 스택이 비었다면 0을 출력해준다.
• n번 반복한다.

Code

#include <iostream>
#include <stack>
#include <vector>
#define MAX 500001
using namespace std;

int n;
int arr[MAX];
stack<pair<int, int>> tops;

void Input(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>arr[i];
    }
}
void Solution(){
    for(int i=1; i<=n; i++){
        while(!tops.empty()){
            if(tops.top().second>arr[i]){
                cout<<tops.top().first<<" ";
                break;
            }
            tops.pop();
        }
        if(tops.empty()){
            cout<<0<<" ";
        }
        tops.push({i, arr[i]});
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}

시간을 초과하지 않고 해결된 것을 확인할 수 있다.

오랜만에 알고리즘 문제를 풀어서 익숙하지 않은 기분을 느꼈다. 다시 꾸준히 알고리즘 문제를 풀어야겠다.