[구름 알고리즘 먼데이 챌린지] Week8 : 2. 뒤통수가 따가워

문제

구름나라의 저편에 있는 무릉도원에는 높은 산봉우리들이 있는 산맥이 있다. 모든 산봉우리에는 동쪽을 바라보며 명상을 하는 신선이 한 명씩 있다. 그러던 중 신선들은 다른 신선들이 자신의 뒤통수를 바라봐서 그런지 뒤통수가 따가워짐을 느끼다가, 문득 얼마나 많은 신선이 자신의 뒤통수를 볼 수 있는지 궁금해졌다. 

 

산맥의 모든 봉우리들은 왼쪽에서 오른쪽으로 정확히 일렬로 놓여있다. 왼쪽에서 a번째 봉우리에 있는 신선이 b번째 봉우리에 있는 신선의 뒤통수를 보기 위해선, a < b이면서 두 봉우리 사이에 있는 모든 봉우리의 높이가 a번째 봉우리의 높이보다 작아야 한다. 중간에 높은 봉우리가 있으면 그 뒤쪽 봉우리는 가려져서 보이지 않기 때문이다.

 

신선들의 궁금증을 해결해주기 위해, 산맥에 있는 봉우리의 개수와 각 봉우리의 높이를 알려주면 각 신선마다 그 신선의 뒤통수를 볼 수 있는 신선의 수를 출력하는 프로그램을 만들어보자.

---

입력

첫 번째 줄에는 봉우리의 수를 나타내는 정수 N(5 <= N <= 100,000)이 주어진다.

두 번째 줄에는 봉우리의 높이가 왼쪽에서부터 순서대로 주어진다. 각 봉우리의 높이는 10^9이하의 양의 정수이다.

---

스택 자료구조를 사용하여 문제를 해결해 주었다.

스택을 사용한 풀이법을 이해하기 쉽게 그림과 함께 설명해보자.

N = 10, mountain = [19, 11, 4, 10, 19, 11, 4, 7, 6, 18] 인 경우 순서대로 살펴보면

 

자신(19)을 스택에 push하기 전 스택의 크기가 자신을 바라보는 신선의 수가 된다. -> 0

 

자신을 스택에 저장하기 전 스택의 사이즈 1을 자신을 바라보는 신선의 수로 출력한 뒤 자신(11)을 push한다. -> 1

마찬가지로 2를 출력후 자신(4)을 push한다. -> 2

3을 출력하고 자신과 같거나 낮은 봉우리는 이후 봉우리를 볼 수 없기 때문에 스택에서 제거해 준 뒤 자신(10)을 push한다.

마찬가지로 3을 출력하고 이전에 모든 봉우리는 자신의 뒤에 오는 봉우리는 쳐다 볼 수 없으므로

스택에서 전부 제거해준뒤 자신(19)을 push한다.

 

위와 같은 과정을 통해 정답을 구할 수 있고 구현 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

stack<int> s;

int main() {
    int i, n;

    cin >> n;
    vector<int> mountain(n, 0);
    for (i = 0; i < n; i++) cin >> mountain[i];

    for (i = 0; i < n; i++) {
        cout << s.size() << ' ';
        while (!s.empty() && s.top() <= mountain[i]) s.pop();
        s.push(mountain[i]);
    }

    return 0;
}