yceffort

Codility - Stone Wall

Published on June 25, 2020

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을 리턴해야 하는데, 그 이유는 아래와 같다.

stone-wall

풀이

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
}

https://app.codility.com/demo/results/trainingTEZQDK-37Z/