백준 2493 - 탑 (C++)

 

 

입력에 대해, 그림과 같은 높이의 송신탑을 그려볼 수 있을 것이다.

이 때, 각 송신 레이더에서 왼쪽으로 레이더를 쏘았을 때 가장 먼저 신호를 수신하는 탑의 인덱스를 출력하면 된다.

그림을 보면, 첫번째와 두번째 송신탑은 신호를 수신할 탑이 왼쪽에 존재하지 않기 때문에 0을 출력하면 된다.

세번째 탑의 경우 두번째 탑이 신호를 수신하고 있으며, 네번째 탑도 두번째 탑이 신호를 수신하고 있다.

마지막 탑의 경우는 네번째 탑이 신호를 수신해주고 있다.

 

그러므로, (0, 0, 2, 2, 4)를 출력하면 되는 문제이다.

 

문제 풀이

 

해당 문제는 전형적인 단조 스택 문제이다. 단조 스택을 잘 모른다면, 여기를 클릭하여 알아보고 다시 오도록 하자,

단조스택을 사용하여 PGE를 구하면 된다.

 

입력에 대해 과정을 한 번씩 훑어보자.

먼저, 맨 앞의 6을 검사할 때, Stack의 Size가 0이었으므로 Answer을 0으로 갱신한 뒤 6을 stack에 push해주었다.

9를 검사할 때엔, Stack의 Top이 현재 값보다 작으므로, 해당 값을 pop해주었다.

stack의 size가 0이 될 때까지 PGE를 찾지 못했으므로, PGE가 없다고 간주하고 Answer을 0으로 갱신한 뒤 9를 스택에 삽입하였다.

5를 검사할 때엔, Stack의 Top이 현재 값보다 크므로, 해당 값에 대한 인덱스로 Answer의 값을 갱신하였다.

이후, Stack에 본인을 삽입하였다.

 

7을 검사할 때엔, 5를 pop하였고 PGE인 9를 찾았으므로 Answer를 9의 인덱스로 갱신하였다.

Stack에 본인도 삽입해주었다.

마지막 4를 검사할 때엔, Stack의 top인 7이 PGE이므로 7의 인덱스인 4로 Answer을 갱신해주었다.

 

단조스택 알고리즘을 그대로 활용하면 되는 문제이다.

단, 이 문제는 값이 아닌 인덱스를 저장하고 출력하는 문제이기 때문에 Stack에 데이터를 삽입할 때, {Data, Index}형태의 pair로 삽입해서 검사해야 한다.

 

코드 풀이

 

먼저, 값을 입력받고 초기화해주었다.

int NumOfTower = 0;
std::cin >> NumOfTower;

std::vector<int> TowerArray(NumOfTower, 0);
std::vector<int> Answer(NumOfTower, 0);

for (int i = 0; i < NumOfTower; i++)
{
    std::cin >> TowerArray[i];
}

std::stack<std::pair<int, int>> MonotonicStack;

 

배열을 초기화한 뒤, 사용할 Stack또한 선언해주었다.

 

다음은 PGE를 구하는 반복문이다.

for (int i = 0; i < TowerArray.size(); i++)
{
    int CurNum = TowerArray[i];

    while (MonotonicStack.size() > 0)
    {
        if (MonotonicStack.top().first > CurNum)
        {
            break;
        }

        MonotonicStack.pop();
    }

    if (MonotonicStack.size() == 0)
    {
        Answer[i] = 0;
    }
    else
    {
        Answer[i] = MonotonicStack.top().second + 1;
    }

    MonotonicStack.push({ CurNum, i});
}

 

 

Stack의 Top이 현재 값보다 큰 값이 나올때까지 반복문을 돌려주었다.

반복문이 끝난 뒤, Stack의 size가 0이라면 PGE를 찾지 못한것이므로 Answer을 0으로 갱신해주었다.

만약, PGE를 찾았다면, 해당 PGE의 인덱스 + 1로 Answer을 갱신해주었다.

(배열의 인덱스는 0부터 시작이지만, 문제에서 송신탑의 번호는 1부터 시작이므로 1을 더해주어야 한다.)

 

마지막으로 Stack에 본인을 삽입해주었다.

 

이렇게 반복문을 모두 돌린 뒤, Answer의 원소를 모두 출력해주면 끝이다.

for (int i = 0; i < NumOfTower; i++)
{
    std::cout << Answer[i] << "\n";
}

 

 

 

참고로, 본인은 문제를 풀 때 Answer을 따로 사용하지 않고 TowerArray의 값을 갱신하면서 풀어보았는데, 동일하게 잘 풀리는 것을 확인하였다. 사용 메모리도 2000kb가량 감소하였다. 다만, 약간의 예외처리가 필요한데 이 것이 설명을 방해할까봐 정석의 방식으로 문제를 해결하였다.

 

코드 전문

 

#include <iostream>
#include <vector>
#include <stack>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumOfTower = 0;
    std::cin >> NumOfTower;

    std::vector<int> TowerArray(NumOfTower, 0);
    std::vector<int> Answer(NumOfTower, 0);

    for (int i = 0; i < NumOfTower; i++)
    {
        std::cin >> TowerArray[i];
    }

    std::stack<std::pair<int, int>> MonotonicStack;

    for (int i = 0; i < TowerArray.size(); i++)
    {
        int CurNum = TowerArray[i];

        while (MonotonicStack.size() > 0)
        {
            if (MonotonicStack.top().first > CurNum)
            {
            	break;
            }

            MonotonicStack.pop();
        }

        if (MonotonicStack.size() == 0)
        {
            Answer[i] = 0;
        }
        else
        {
            Answer[i] = MonotonicStack.top().second + 1;
        }

        MonotonicStack.push({ CurNum, i});
    }

    for (int i = 0; i < NumOfTower; i++)
    {
        std::cout << Answer[i] << "\n";
    }

    return 0;
}