백준 2493번: 탑, c++

 

 

처음에 작성한 코드는 다음과 같다.

하지만 시간초과가 나왔다.

중첩 for문에서 시간복잡도가 O(n^2)가 되어 오류가 난 것 같다.

#include <iostream>
using namespace std;

int main(){
    int N;
    cin >> N;
    
    int arr[N];
    int result[N+1] = {0,};
    for(int i=1; i<=N; i++)
        cin >> arr[i];
    
    for(int i=N; i>=2; i--) {
        for(int j=i-1; j>=1; j--) {
            if(arr[j] >= arr[i]) {
                result[i] = j;
                break;
            }
        }
    }
    
    for(int i=1; i<=N; i++)
        cout << result[i] << " ";
    return 0;
}

 

 

 

시간 복잡도 문제를 해결해야 했다.

구글링을 했더니 보통 스택으로 시간복잡도 문제를 해결했음을 알 수 있었다.