[Jungol] 정올 1328 빌딩

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=607&sca=3020 

Approach

원래 빌딩에서는 내려다보면 낮은 높이의 빌딩도 보이겠지만 해당 문제는 빌딩 옥상에서 정면만 응시하는 것입니다.

그렇기에 Hi < Hj 일 경우, i번 빌딩에서 j번 빌딩을 볼 수 있다. ( i < j )

- 첫번째 입력 Data는 Stack에 비교 데이터가 없으므로 push

   (스택이 비워져 있는 경우에는 입력 데이터 push)

- 입력 데이터 push 전에 스택이 비워져 있지 않은 경우

    입력 데이터 값(높이) 보다 작은 값(top)들 pop() 처리

    이때, pop() 되는 빌딩들이 볼 수 있는 가장 가까운 빌딩인 현재 입력 데이터 순서입니다.

 

▶  [스택] Stack 이란? 

[스택] Stack 이란?

 

Input Data

건물 6개 : 3 → 2 → 6 → 1 → 1 → 2

① stack = [] / 입력 데이터 = 3

    → 스택이 비워져 있으므로 push(3)

② stack = [3] / 입력 데이터 = 2

    → top() = 3 ≥ 2 이므로 push(2)

③ stack = [3 2] / 입력 데이터 = 6

    → top() = 2 < 6 이므로 두번째 빌딩에서 볼 수 있는 빌딩의 위치는 세번째 빌딩 pop()

    → top() = 3 < 6 이므로 첫번째 빌딩에서 볼 수 있는 빌딩의 위치는 세번째 빌딩 pop()

    → 스택이 비워졌으므로 push(6)

    * 스택에는 현재 들어온 높이보다 크거나 같은 데이터만 남아 있습니다.

④ stack = [6] / 입력 데이터 = 1

    → top() = 6 ≥ 1 이므로 push(1)

⑤ stack = [6 1] / 입력 데이터 = 1

    → top() = 6 ≥ 1 이므로 push(1)

    → top() = 1 ≥ 1 이므로 push(1)

⑥ stack = [6 1 1] / 입력 데이터 = 2

    → top() = 1 < 2 이므로 네번째 빌딩에서 볼 수 있는 빌딩의 위치는 여섯번째 빌딩 pop()

    → top() = 1 < 2 이므로 다섯번째 빌딩에서 볼 수 있는 빌딩의 위치는 여섯번째 빌딩 pop()

    → top() = 6 ≥ 2 이므로 push(2)

모든 입력 데이터가 종료되고 stack = [6 2]가 남아있느 상태에서는 

해당 데이터(빌딩)에서는 보이는 빌딩이 없는 것이므로 『0』으로 저장됩니다.

※ 스택에는 가 저장됩니다.

 

---

#include <stdio.h>
 
const int MAX_N = 100000;
int ansList[MAX_N + 10];
struct Stack {
    int height, idx;
}stack[MAX_N + 10];
int sp;
 
void push(int data, int idx) {
    stack[++sp] = { data, idx };
}
Stack top() { return stack[sp]; }
void pop() { sp--; }
bool isEmpty() { return sp == 0;}
int size() { return sp; }
 
int main() {
    // freopen("input.txt", "r", stdin);
 
    int h, N; scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &h);
        
        if (isEmpty()) {
            push(h, i);
            continue;
        }
        
        // 스택이 비워있지 않은 경우
        // top()과 높이 비교
        while (!isEmpty() && top().height < h) {
            ansList[top().idx] = i;
            pop();
        }
        push(h, i);
    }
 
    while (!isEmpty()) {
        ansList[top().idx] = 0;
        pop();
    }
 
    for (int i = 1; i <= N; ++i) {
        printf("%d\n", ansList[i]);
    }
}