빌딩2

문제 설명

---

N개의 빌딩이 있다.
빌딩은 1번부터 N번까지 번호가 붙어 있다.
빌딩은 X좌표 상에 위치해 있으며 i번 빌딩은 i좌표 상에 위치해 있다. 그리고 각 빌딩은 Hi 만큼의 높이를 가지고 있다.
i < j 이고 Hi < Hj 일 경우, i번 빌딩에서 j번 빌딩을 볼 수 있다.
각 빌딩에서 현재 빌딩의 좌표보다 뒤에 있는 빌딩을 보고자 할 때, 가장 가까이 보이는 빌딩이 어딘지 찾는 프로그램을 작성하라.

입력 설명

---

입력의 첫 번째 줄에는 N이 입력된다(1≤N≤100,000).
그리고 그 다음 줄부터는 Hi(1≤Hi≤1,000,000)가 순서대로 한 줄에 하나씩 입력된다.

출력 설명

---

총 N개의 줄에 출력을 하게 되며, i번째 줄에는 i번 빌딩에서 보이는 가장 가까운 빌딩의 번호를 출력한다.
만약에 보이는 빌딩이 없을 경우에는 0을 출력한다.

입력 예시

---

6
3
2
6
1
1
2

출력 예시

---

3
3
0
6
6
0

#include <stdio.h>
#define MAXN ((int)1e5)
int N;//빌딩수
int H[MAXN+10];//빌딩높이
int sol[MAXN+10];//각 빌딩에서 보이는 빌딩 번호
 
//FA stack
int stk[MAXN+10];//보이는 빌딩을 못 찾은 빌딩 번호
int sp;
void push(int n) { stk[++sp] = n; }
void pop(void) { sp--; }
int top(void) { return stk[sp]; }
int empty(void) { return sp==0; }
int size(void) { return sp; }
 
void Solve(void){
    sp = 0;
    for (int i=1; i<=N; i++){
        //1.스택에 i번 빌딩보다 낮은 빌딩은 i번 빌딩을 봄(저장, 제거)
        while(!empty() && (H[top()] < H[i])){
            sol[top()] = i;
            pop();
        }
        //2.i번 빌딩은 스택에 저장
        push(i);
    }
}
 
void SolveN2(){//O(N^2), 시간 초과 발생
    for (int i=1; i<=N; i++){
        for (int j=i+1; j<=N; j++){
            if (H[i] < H[j]) {
                sol[i] = j;
                break;
            }
        }
    }
}
 
void InputData(void) {
    scanf("%d", &N);
    for (int i=1; i<=N; i++){
        scanf("%d", &H[i]);
    }
}
void OutputData(void) {
    for (int i=1; i<=N; i++){
        printf("%d\n", sol[i]);
    }
}
 
int main(void) {
    InputData();//입력받는 부분
 
    //SolveN2();//시간초과 발생
    Solve();//여기서부터 작성
 
    OutputData();//출력하는 부분
    return 0;
}