[백준 2493번] 탑

🔗알고리즘 문제

이 문제는 스택 자료구조를 사용하여 해결할 수 있는 문제로 스택 자료구조에 대한 완벽한 이해를 할 수 있도록 도와준 좋은 문제였다.

문제 분석

문제가 굉장히 길지만 문제의 핵심은 결국 높이가 다른 n개의 탑에서 각각 레이저를 발사하는데 어느시점에서 레이저가 막히는지 알아내는 문제이다.

각 인덱스의 위치에 레이저가 막혔다면 막힌 탑의 인덱스를 출력하고 아니라면 0을 출력하면 된다.

위에 사진처럼 오른쪽부터 순서대로 6, 9, 5, 7, 4 높이의 탑들이 있다면 높이가 4인 탑에서 쏜 레이저는 높이가 7인 탑에 막히고 높히가 7인 탑에서 쏜 레이저는 높이가 9인 탑에 막히고 . . . .

결국 순서대로 0, 0, 2, 2, 4 이런식으로 레이저가 막히게 된다.

발상

문제를 보자마자 든 생각은 레이저를 담고있는 자료구조를 만든 후 각각 for문을 돌리며 레이저가 어디서 막히는지 판단하는 방식으로 문제를 해결해야겠다고 생각했다.

처음에 생각한 방법은 다음과 같은데

1. 각 탑의 높이를 담은 배열 생성
2. 배열을 돌리며 레이저 계산하기
    ㄴ 배열을 돌며 제일 큰 탑을 저장해두기
    ㄴ 현재 입력된 탑이 가장 높은 탑이라면 0 반환
    ㄴ 아니라면 가장 높은 탑에서 막히도록
3. 답 출력

가장 큰 탑을 저장해두고 계산을 하기 때문에 9, 7, 4 이와 같은 배열에서 4가 7에서 막히지 않고 9에서 막히는 이슈가 생겼다.

만약, 가장 큰 탑을 지정하지 않고 배열에서 for문을 돌며 계산한다고 해도 배열의 크기를 다 돌아야 하기에 시간초과 이슈를 해결할 수 없어 다른 방법을 생각하였다.

1. pair<int, int>를 담는 stack을 만들기
2. 레이저 계산
    ㄴ pair의 first에는 탑의 높이, second에는 탑의 인덱스 번호를 넣게 됨
    ㄴ 레이저가 막힐 때까지 pop을 시켜주며 답 추출

스택의 값이 이미 자신의 인덱스와 높이를 알고 있기에 for문으로 찾을 필요가 없어 시간복잡도도 해결하며 문제를 해결 할 수 있었다.

알고리즘 설계

1. 현재 인덱스의 탑의 높이를 입력받기
2. 현재 스택의 top이 레이저를 막을 때까지 while문을 통해 스택의 값을 pop해줌
3. 타워에 현재 인덱스의 탑의 높이와 인덱스를 push 해준다.

코드

#include<iostream>
#include<stack>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    int top_count;
    stack<pair<int, int>> towers; 

    cin >> top_count;

    for(int i = 0; i < top_count; i++){
        int height;
        int answer = 0;
        cin >> height;

        while(!towers.empty() && towers.top().first < height) towers.pop();
        if(!towers.empty()) answer = towers.top().second + 1;
        towers.push(pair<int, int>(height, i));

        cout << answer << " ";
    }
}