[백준 BOJ][stack] 2493 탑

2493_탑

링크

https://www.acmicpc.net/problem/2493

 

풀이

 

각 레이저가 왼쪽으로 얼마나 뻗을 수 있는지 체크하기 위해서 스택을 사용해 풀 수 있습니다.

 

이 문제에서는 내림차순 스택을 사용하면 되는데요.

시작을 1번지라고 두고 1번지부터 n번지까지 스택에 내림차순을 유지하면서 집어넣는 것입니다. 스택 내부의 번지들은 현재 i번째 탑이 발사한 레이저 신호를 수신할 가능성이 있는 탑을 의미합니다.

i번째 탑의 높이가 바로 스택의 top번째 탑의 높이보다 작거나 같다면 발사한 레이저는 바로 왼쪽 탑이 수신할 것이므로 left[i]는 top이 됩니다. 그리고 이제 i번째 탑이 수신할 가능성이 제일 높으니 i를 push합니다.

 

i번째 탑의 높이가 스택의 top번째 탑의 높이보다 크다면 top번째 탑 위로 날아가겠죠? 그러니 top을 pop 해줍니다. 그러다가 i번째 탑의 높이가 스택의 top번째 탑의 높이보다 작거나 같다면 그때 탑이 수신할 것이므로 left[i]는 top이 됩니다. 그리고 i를 push합니다.

 

만약 스택이 empty라면 레이저 신호는 수신되지 않으므로 left[i]는 0이 되고, i를 push합니다.

 

(n부터 1까지 돌린다면 pop할 때 left에 값을 채워주고, 스택에 남은 번지들에 0을 넣어주면 됩니다.)

 

코드

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

//2493_탑 #include <cstdio> #include <stack> #include <algorithm> using namespace std;   int n; int h[500001], left[500001], ans;   stack<int> stk;     int main() {       scanf("%d", &n);       for (int i = 1; i <= n; ++i) {         scanf("%d", &h[i]);     }       for (int i = 1; i <= n; ++i) {    //왼쪽으로 뻗을 수 있는 정도         int tmp;           while (true) {             if (!stk.empty()) {                 tmp = h[stk.top()];             }             else {                 tmp = -1;             }               if (tmp < h[i] && tmp != -1) stk.pop();             else {                 if (stk.size() == 0) {                     left[i] = 0;                     stk.push(i);                     break;                 }                 else {                     left[i] = stk.top();                     stk.push(i);                     break;                 }             }         }     }       for (int i = 1; i <= n; ++i) {         printf("%d ", left[i]);     }       return 0; } Colored by Color Scripter

cs