[백준 2493][C++] 탑

이 문제에서 배운 것들 정리

 

• 시간복잡도 계산

내 코드의 경우 N 개의 입력에 대해서 O(N^2)인 것은 맞는 것 같다. (빅 오 표기법의 경우 최악의 경우를 따지므로) 하지만 실제로 이런 케이스는 N개의 입력 각각이 모두 N^2번의 연산을 하는것이 아니기 때문에 테스트 케이스를 통과하는 것이 아닐까 싶다.

모든 입력이 N^2번의 연산을 하지 않는 이유는 스택에서 삭제하는 연산 때문에 검사해야할 스택 크기 자체가 줄어들기 떄문이다.

알고보니 O(N)짜리 코드였다. 스택에 넣고, 삭제하는 연산을 N번 만큼 하기 때문!!

유의할 점은 이중 반복문이라고 해서 N^2이라고 생각하면 안된다는점.

 

참고 링크 : https://www.acmicpc.net/board/view/9807

글 읽기 - 탑 문제 - 시간복잡도

• 입력, 출력의 테스트 케이스가 많은 경우 cin, cout은 매우 느리므로 사용 X

 

#include <stdio.h>
#include <stack>
#include <utility>
 
using namespace std;
int main() {
    int N;
    scanf_s("%d", &N);
    stack<pair<int, int>> s; // value, index
    for (int i = 0; i < N; i++) {
        int curHeight;
        scanf_s("%d",&curHeight);
        while (!s.empty() && s.top().first <= curHeight)
            s.pop();
        if (s.empty()) 
            printf("0 ");
        else
            printf("%d ",s.top().second + 1);
        s.push(make_pair(curHeight, i));
    }
}