알고리즘 > 자료구조A > 빌딩(1328)

1. Question

문제 보기

2. Solving

쉬워보여 바로 코딩했다 마지막 Test case에서 Time limit이 걸려버렸다.

다양한 풀이법이 있을 수 있지만, Stack을 이용하니 O(n)의 속도가 되어 마지막 Test case도 통과할 수 있었다.

input으로 들어오는 빌딩의 높이가 3 2 6 1 1 2 라면,

1) 일단 첫번째 수를 Push

3

2) top보다 작거나 같은 수가 나오면 push, 새로운 수가 top보다 큰 수가 나오면 top이 새로 들어올 수보다 클 때까지 pop하고 새로운 수를 push한다. 

2가 3보다 작기 때문에 push했다.

2

3

3) 6이 들어올 차례이다. 2가 6보다 작기 때문에 pop, 3도 pop, 그리고 6을 push한다.

6

               

4) 마찬가지 방법으로...push pop을 반복하면 아래와 같은 과정으로 스택이 변화한다.

6 1  -> 6 1 1 -> 6 2

5) 마지막까지 스택에 남아있는 6과 2의 자리는 0으로 출력하면 된다.

3. Code

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

#include <stdio.h> #include <stack> #pragma warning(disable:4996)   using namespace std;   typedef struct _node {     int h;     int num; }node; int n, order[100005]; node arr[100005];   int main() {     FILE *fin = fopen("input.txt", "rt");     FILE *fout = fopen("output.txt", "wt");       fscanf(fin,"%d", &n);     //scanf("%d", &n);     for (int i = 1; i <= n; i++)     {         fscanf(fin,"%d", &arr[i].h);         //scanf("%d", &arr[i].h);         arr[i].num = i;         order[i] = -1;     }       stack<node> st;     int cnt = 1, bottom = 0;     for (int i = 1; i <= n; i++)     {         if (order[i] != -1)             continue;         if (st.empty())         {             bottom = arr[i].h;             st.push(arr[i]);         }         // top보다 작거나 크면 push         else if (arr[i].h <= st.top().h)         {             st.push(arr[i]);         }         // top         else if (arr[i].h > st.top().h)         {             while (!st.empty() && !(arr[i].h <= st.top().h))             {                                 if (arr[i].h <= st.top().h)                 {                     st.push(arr[i]);                 }                 else                 {                     // 저장하고, 뺀다.                     order[st.top().num] = i;                     st.pop();                 }             }             if (st.empty())             {                 st.push(arr[i]);                             }             else             {                 st.push(arr[i]);             }         }     }       for (int i = 1; i <= n; i++)     {         if (order[i] == -1)         {             fprintf(fout, "%d\n", 0);             /*printf("%d\n", 0);*/         }         else         {             fprintf(fout, "%d\n", order[i]);             //printf("%d\n", order[i]);         }     } }