옥상 정원 꾸미기
📚 문제 설명
도시에는 N개의 빌딩이 있다.
빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.
i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.
예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우
=
= =
= - =
= = = -> 관리인이 보는 방향
= - = = =
= = = = = =
10 3 7 4 12 2 -> 빌딩의 높이
[1][2][3][4][5][6] -> 빌딩의 번호- 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
- 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
- 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
- 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.
따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.
결론은 앞서 말한 관리인들이 옥상정원을 확인할 수 있는 총 수를 출력하는 문제이다.
👨🏻💻 풀이 과정
해당 문제를 처음 접했을 때 왜 이 문제가 골드 문제인지 이해할 수가 없었다.
단순이 반복문을 사용하여 계산을 해주면 되는 것이 아닌가.
이렇게 생각하며 일단 생각나는대로 한번 풀어보자 하며, 틀릴 것을 각오하고 풀어보았다.
그리하여 생각한 첫번째 풀이
forEach(Value,Index,function())을 이용하여 풀자.- 반복문을 사용하여
Index보다 높은 인덱스 들을 확인.cnt변수를 이용하여Value보다 작은 값만 카운트.- 다음 값이
Value보다 크면 반복문 종료
answer에cnt값 더해줌.
첫번째 풀이
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);
let n = input.shift();
let answer = 0;
input.forEach((Value, Index) => {
let cnt = 0;
if (Index !== input.length - 1) {
for (let i = Index + 1; i < input.length; i++) {
if (Value > input[i]) {
cnt++;
}else break;
}
answer += cnt;
}else {
answer += cnt;
}
});
console.log(answer);원래 앞에서 말했듯, 틀릴 것을 가정하고 생각나는 대로 풀었던 풀이인데 맞았다고 떴다.
이 풀이가 맞는건지 궁금해서 다른 분들의 코드를 확인해 봤는데 다른 분들은 Stack을 이용하여 풀었다는건 이해가 되었지만, 왜 그런 풀이가 나왔는지 도저히 이해가 안됬다.
그래서 알아본 결과, 그 풀이들은 Monotonic Stack 알고리즘 이라는 것을 사용하여 풀었던 것이다.
💡 Monotonic Stack 알고리즘
Monotonic Stack 알고리즘은 스택을 오름차순(Increasing) 또는 내림차순(Decreasing)으로 정렬해주는 알고리즘이다.
Monotonic Stack의(Decreasing 배열) 구현은 다음과 같다.
[10, 3, 7, 4, 12, 2] 라는 배열이 있고 Stack이 빈배열[]로 있다고 가정하고 내림차순으로 만들어보자.
- 우선 스택에 10을 PUSH
[10]
- 스택의 최상단 확인
- 10은 3보다 크다. 따라서 3을 PUSH
[10, 3]
- 이제 7을 넣어야하는데 그전에 Stack의 최상단을 확인한다.
- 스택의 최상단은 3이니까 7보다 작다. 따라서 POP
- 그 후 스택의 최사단인 10은 7보다 크다. 따라서 스택에 7을 PUSH
[10,7]
- 스택의 최상단 확인.
- 7은 4보다 크다. 따라서 4를 PUSH
....생략그런데 이런 작업이 무슨 의미가 있을까?
사실 이런 작업의 결과는 별 의미 없다고 한다.
그러나 해당 과정 속에 있는 각각의 Stack은 여러가지 의미를 갖는다고 한다.
그럼 위의 Monotonic Stack(단조 스택)을 이용하여 해당 문제를 풀어보면 각각의 Stack이 무슨 의미를 갖는지 확인해 보자.
(앞에서 설명한 Monotonic Stack을 만드는 과정은 이제 일일히 설명하지 않겠다.)
해당 문제에서 건물을 모두 내림차순으로 정렬되도록 Stack 을 만들면 다음과 같은 순서로 Stack 에 들어간다.
[10]
[10, 3]
[10, 7]
[10, 7, 4]
[12]
[12, 2]
이렇게 보면 각각의 Stack 이 어떤 의미가 있는지 보기 쉬울 수도 있다.
바로 모든 Stack 은 최상단의 건물을 기준으로 자기 자신을 바라보고 있는 건물들을 의미한다.
따라서 각각의 Stack.length - 1 은 스택의 최상단 건물을 쳐다보는 건물의 수이다.
(stack.length - 1로 계산)
[10] - 10을 바라보는 건물은 0 개
[10, 3] - 3을 바라보는 건물은 1개
[10, 7] - 7을 바라보는 건물은 1개
[10, 7, 4] - 4를 바라보는 건물은 2개
[12] - 12를 바라보는 건물은 0개
[12, 2] - 2를 바라보는 건물은 1개
따라서 위의 Monotonic Stack(단조 스택)을 이용하여 해당 문제를 풀면 다음과 같다.
Monotonic Stack(단조 스택)을 이용한 풀이
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);
let n = input.shift();
let Stack = [];
let answer = 0;
// 건물을 첫번째부터 확인
for (let i = 0; i < input.length; i++) {
// 만약 스택의 최상단보다 다음 값이 클 경우 pop 진행
while (Stack.length) {
if (Stack[Stack.length - 1] <= input[i]) {
Stack.pop();
}else break;
}
Stack.push(input[i]);
// Stack.length - 1이 바로 해당 건물(input[i])을 바라보는 건물의 수
answer += Stack.length - 1;
}
console.log(answer);
앞선 풀이보다 시간이 확실하게 줄어든 것을 확인할 수 있었다.
그러나 Monotonic Stack(단조 스택)을 이용한 풀이는 Stack 을 이용하기 위해 배열을 따로 만들었기 때문에 메모리는 좀 더 사용하는 것으로 보인다.
🧐 후기
정말 간단한 문제라고 생각했는데 생각보다 이해하는데 어려운 알고리즘이 들어가 있어서 매우 당황했다.
그리고 Monotonic Stack(단조 스택)을 일단 지금은 이해했지만, 이것을 활용해서 다른 문제를 풀 수 있는가에 대한 것은 또 다른 말인 것 같다. 따라서 Monotonic Stack(단조 스택)을 사용해야하는 문제들을 앞으로 좀 더 찾아보며 해당 알고리즘 사용에 익숙해지는 과정이 필요해 보인다.
