All Posts
Codility - Stone Wall
StoneWall
문제
돌은 N미터 길이를 가지고 있으며, 두께는 모두 일정하다. 배얼에 돌 높이가 주어져 있으며, 아래와 같이 해석할 수 있다.
- H[i]: 왼쪽에서 오른쪽으로 벽의 높이
- H[0]: 벽 왼쪽 끝의 높이
- H[N-1]: 벽 마지막 끝의 높이
H[0] = 8 H[1] = 8 H[2] = 5
H[3] = 7 H[4] = 9 H[5] = 8
H[6] = 7 H[7] = 4 H[8] = 8
는 7을 리턴해야 하는데, 그 이유는 아래와 같다.
풀이
function solution(H) {
const stack = []
let count = 0
for (let i=0; i<H.length; i++) {
// 베이스가 돌을 찾는다.
// 베이스가 될 돌은 무조건 하나 있어야 하고
// 현재 쌓으려는 돌 위치보다 낮아야 한다.
while (stack.length > 0 && stack[stack.length-1] > H[i]) {
stack.pop()
}
// 돌 명단이 비어있거나, 새로 쌓아야 할 돌이 스택의 마지막 돌 보다 높다면 새로 쌓는다.
if (stack.length === 0 || stack[stack.length-1] < H[i]) {
// 새로 쌓고 지금 높이를 리턴한다.
stack.push(H[i])
count += 1
}
}
return count
}