[백준 2493번] 탑

문제 링크: https://www.acmicpc.net/problem/2493

2493번: 탑

문제 풀이

첫 번째 탑에서 시작해서 탑을 두 개씩(i, i+1) 이용하면 스택으로 문제를 해결할 수 있습니다. 

 

 

스택을 하나 준비해서 탑의 번호를 저장합니다

이때 스택의 top()은 i번쨰 탑이 레이저를 발사했을 때 수신받을 수 있는 가장 가까운 탑입니다.

 

수신받을 수 있는 탑이 없는 경우는 높이가 0인 0번째 탑이 존재한다고 생각하고 0번째 탑이 수신하도록 하면 됩니다.

 

이제 i번째와 i+1번째 탑 두 개를 이용해서 다음과 같은 알고리즘을 만들 수 있습니다.

1. 만약 i+1번째 탑이 i번째 탑보다 크다면

-> 스택의 top()이 i+1번쨰 탑보다 클 때까지 스택을 pop()합니다

  ->스택의 top()이 i+1 번째 탑보다 작으면 top()이 i+1번째 탑의 레이저를 수신하지 못합니다.

  (단 스택의 top() > 0 이상일 때입니다. 왜냐하면 아무것도 수신받는 레이저가 없을 땐 0번째 탑이 수신하도록 했습니다.

2. 그렇지 않으면 만약 i+1번째 탑이 i번째 탑보다 작으면

-> i번째 탑을 스택에 push()합니다.

  -> i번쨰 탑이 i+1번째의 탑의 레이저를 수신하게 만듭니다.

 

3. 그렇지 않으면 만약 i+1번째 탑이 i번쨰 탑보다 작으면

-> 스택을 pop()하고 i번쨰 탑을 스택에 push()합니다.

  -> i+1번째 레이저를 가장 가까운 탑이 수신하도록 합니다.

 

문제의 입력을 예로 설명하면

i = 1일 때

0번째 탑이 1번째 탑의 레이저를 수신합니다.

 

i = 2일 때

1번째 탑이 2번째 탑의 레이저를 수신하고 2번째 탑을 스택에 push()합니다.

 

i = 3일 때

2번째 탑이 3번째 탑의 레이저를 수신합니다.

 

i = 4일 때

2번째 탑이 4번째 탑의 레이저를 수신하고 4번째 탑을 스택에 push()합니다.

 

i = n일 때

4번째 탑이 5번째 탑의 레이저를 수신합니다.

 

 

 

<C++ 소스 코드> 스택, 자료구조

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int height[500001];
int res[500001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    stack<int> big;
    for (int i = 1; i <= n; i++) {
        cin >> height[i];
    }
 
    big.push(0);
 
    for (int i = 1; i < n; i++) {
        res[i] = big.top(); //스택에 top()은 i번째 레이저를 수신
        if (height[i + 1] > height[i] && big.top()) {
            while (height[big.top()] < height[i + 1] && big.top()) {//스택의 top()이 i+1번째 탑보다 커야 하므로 작은 top()은 제거
                big.pop();
            }
        }
        else if (height[i + 1] < height[i]) {
            big.push(i);//i번째 탑을 i+1번째 탑이 만나는 가장 가까우면서 큰 탑으로 만듬
        }
        else if (height[i + 1] == height[i]) { // 연속된 크기의 탑일 경우엔 가장 가까운 탑이 수신하도록 함
            big.pop();
            big.push(i);
        }
    }
    res[n] = big.top();
    for (int i = 1; i <= n; i++) {
        cout << res[i] << " ";
    }
 
 
    return 0;
}