[c++] 프로그래머스 :: 탑 (문제 풀이, 코드)

탑

https://programmers.co.kr/learn/courses/30/lessons/42588?language=cpp

 

코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> heights) {
    int heights_len = heights.size();
    vector<int> answer(heights_len);
    stack<int> stk; // index, key

    for (int i = heights_len - 1; i>0; i--) {
        if (heights[i - 1] > heights[i]) {
            answer[i] = i;

            // stack
            while (stk.size() != 0) {
                auto tmp = stk.top();
                if (heights[tmp] < heights[i - 1]) {
                    answer[tmp] = i;
                    stk.pop();
                }
                else
                    break;
            }
        }
        else {
            stk.push(i);
        }
    }

    int len = stk.size();
    while (len-- > 0) {
        auto tmp = stk.top();
        stk.pop();
        answer[tmp] = 0;
    }

    return answer;
}

 

설명

 탑은 자신보다 크고, 앞에 있는 탑에게만 신호를 전송할 수 있다. 뒤쪽 탑부터 앞쪽 탑으로 가면서 어떤 탑에게 신호를 전송할 수 있는지 살펴보자.

 

 5번 탑부터 살펴보자. 우리는 그림을 직관적으로 보았을 때, 5번 탑 앞에 있는 탑들이 모두 5번 탑보다 작은 것을 알 수 있다. 따라서 5번 탑은 어떤 탑에게도 신호를 보내지 못한다. 그림을 그려놓고 보면 손쉽게 이 사실을 알 수 있지만, 사실 프로그램 상에서는 앞선 모든 탑의 높이를 현재 탑의 높이와 비교해보는 것과 같다. 이러한 방식은 간단하여 실제로 heights가 100이하인 해당 문제에서 10^4 만큼의 시간복잡도를 가진다.

 

 하지만 보다 간단한 방법을 찾아보자.

 하나씩 끊어서 규칙을 찾아보면, 두 개의 탑이 있을 때 앞선 탑이 뒤의 탑보다 작거나 같으면 뒤의 탑은 앞선 탑에게 신호를 전송할 수 없다. 반대로 앞선 탑이 더 크다면 뒤의 탑은 앞선 탑에게 신호를 전송할 수 있다.

 

 이 규칙을 이용해서 여러 탑이 존재할 때를 살펴보자.

 뒤에서부터 앞으로 오면서 살펴보면, 4번 탑은 3번 탑보다 크거나 같은 조건을 만족하므로 3번 탑에 신호를 전송할 수 없다. 하지만 2번 탑보다는 작으므로 2번 탑에 신호를 전송할 수 있다. 이미 2번 탑에 신호를 전송했으므로 1번 탑과의 관계는 살펴볼 필요가 없다.

 

 이렇게 탑이 여러개일 때는 앞선 탑과의 1:1 관계를 신호를 전송할 수 있는 탑까지만 조사하면 된다. 다만 현재의 방법은 (4,3)조사 => (4,2)조사 => (3,2) 조사 => (2,1) 조사 의 순서이다. 이를 스택을 이용해서 약간 순서를 바꿔보면 훨씬 간편하게 구현할 수 있다.

 

 현재 탑보다 한칸 앞에 있는 탑이 작거나 같으면 스택에 저장하고, 그렇지 않다면 정답배열에 답을 저장하기로 하자. 그렇다면 위의 그림에서는 4가 스택에 저장되어있을 것이다. 3번 탑으로 넘어가서 똑같이 비교해본다면 2번 탑은 3번 탑보다 크므로 3번 탑의 정답은 2이다. 이 때, 스택에 들어있던 4번 탑과도 비교를 해본다. 2번 탑이 4번 탑보다 크므로 4번 탑의 정답도 2이다. (4,3)조사 => (3,2)조사 => (4,2)조사 => (2,1)조사 순으로 바꾸는 것이다.

 

이렇게 스택을 이용하는 방법은 다음과 같은 상황에서 유리하다.

 스택을 이용하지 않는 방법이었다면, (6,5)=>(6,4)=>(6,3)=>(6,2)를 조사해야하는 것을 스택 사용 후, (6,5)=>(6,2)로 줄여주기 때문이다. 실제로 세어보면 11번의 비교에서 8번의 비교로 줄어든 것을 알 수 있다.