[BOJ] 백준 2493번 탑 - C++ 코드, 해설, 풀이

백준 2493번 탑 문제 풀이입니다.

2493번: 탑 (acmicpc.net) 

2493번: 탑

 

2009 정올 초등부, 고등부 문제입니다.

직전에 포스팅했던 '옥상 정원 꾸미기'와 유사점이 많은 문제입니다.

 

문제 요약 및 분석

오른쪽에서 왼쪽으로 레이저를 발사하는데 탑의 기둥부분(벽면)에 맞으면 수신이 되는 방식입니다. 높이가 다른 각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지가 문제입니다.

이때 N = 5 x 10^5 으로 O(n)이나 O(NlogN) 안에는 들어와야 시간초과가 나지 않습니다.

이전 포스팅에서도 사용되었던 알고리즘인 '모노톤 스택'을 활용하면 풀 수 있는 문제입니다.

 

예제 입력

풀이방법

왼쪽부터 빌딩의 높이를 비교하는데, stack을 이용해줍니다. 이때 방법은 i번째 탑의 차례에서

1. top이 자기보다 작으면 pop

2. 자기보다 크면 top에 해당되는 탑의 idx+1을 출력

3. 자기 자신을 인덱스와 함께 push

를 반복할 수 있습니다.

이때 0번째 index에는 INF 높이의 임의의 빌딩이 있다고 가정하면 쉽게 구현을 할 수 있습니다.

 

정답 중 핵심코드

void solve() {
    string s, strn;
    stack<pll> stk;
 
    cin >> n;
    vector<int> v(n);
    for (i = 0; i < n; i++) {
        cin >> v[i];
    }
    stk.push(make_pair(INF, 0));
    for (i = 0; i < n; i++) {
        while (!stk.empty()) {
            if (stk.top().first > v[i]) {
                cout << stk.top().second << " ";
                stk.push(make_pair(v[i], i + 1));
                break;
            } else {
                stk.pop();
            }
        }
    }
    cout << endl;
}

이때 stack을 pair<int, int>로 구성해서 first에서는 탑의 높이, second에서는 탑의 index를 저장하고 있습니다.

line 10에서는 0번째 index에 임의의 높이가 INF인 빌딩을 넣어주고 시작해서 구현을 용이하게 합니다.

line 13~ 15의 순서를 유의하면 쉽게 풀 수 있습니다.