[Algorithm][Stack][정올] 1328 : 빌딩

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

순서

I. 문제
II. 접근
III. 구현

---

I. 문제

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

 

---

II. 접근

---

1. O(N^2)

가장 가까이 보이는 빌딩은

"나보다 크고 가장 가까운 빌딩"

현재 위치부터 순차적으로 탐색하면서
나보다 큰 빌딩이 나왔을 때 출력이다.

그렇다면 시간은 거의 N제곱으로
약 10의 9~ 10제곱이라 애~매하다!!

---

2. O(N)

"Stack"이용

순차적으로 탐색을 하지만 한 번에 끝내는 방법!

순서
1. 현재부터 탐색 시작
2. 나보다 작으면 스택에 넣음
3. 다음으로 넘어감
4. 스택의 top과 높이 비교
4-1. top보다 작으면 스택에 넣고 넘어감
4-2. top보다 크면 pop, 다음 스택의 top과 비교(반복)

순서(그림)

 

---

III. 구현

이번 코드에서 시간적인 문제가 존재한다.

c++의 표준 입출력 (cout, cin)이 c의 표준 입출력 (scanf, printf)보다 느리다.

체감은 크지 않지만 이 코드가 반복(이 문제에서 10만번)되면 차이가 커지게된다.따라서 이번 문제도 cin, cout으로 하면 Timeout이고 scanf, printf로 하면 Success이다.

</hide>
#include <stdio.h>
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

struct stu_building{
    int order;
    int H;
};

stack<stu_building> stk;

int N;
int H[100000+10];
int ansArr[100000+10];

void input(){
    memset(H,0,sizeof(H));
    memset(ansArr,0,sizeof(ansArr));
    
    cin>>N;
    for(int i=1;i<=N;i++){
        //cin>>H[i]; 10만번 입력받으면 cin이 눈에 띄게 느리다
        scanf("%d",&H[i]);
    }
}

void solve()
{
    
    stk.push(stu_building{1,H[1]});
    
    for(int i=2;i<=N;i++) // 쭉 탐색
    { 
        while(!stk.empty()) // 스택 쭉 반복해서 비교
        {
            if(stk.top().H < H[i]) // 큰 빌딩이 나오면 
            {
                ansArr[stk.top().order] = i; // 빌딩 위치 저장
                stk.pop(); // 스택에서 빼기
            }
            else break; // 빌딩이 더 작으면 while() 빠져 나옴
        }
        stk.push(stu_building{i,H[i]}); // 현재 확인한 빌딩 push
    }
    
}

int main()
{
    input();
    solve();
    for(int i=1;i<=N;i++) {
        //cout<<ansArr[i]<<endl; 표준 입출력 느리다.
        printf("%d\n",ansArr[i]); // 빠르다.
        
    return 0;
}