269. StoneWall



1. JavaScript


참고, 참고2




// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(H) {
    // write your code in JavaScript (Node.js 8.9.4)
    let stack = [];
    let count = 0;
  
  	
    for(let i = 0; i < H.length; i++){
        // 베이스가 돌을 찾는다.
        // 베이스가 될 돌은 무조건 하나 있어야 하고
   	// 현재 쌓으려는 돌 위치보다 낮아야 한다.
        while (stack.length > 0 && H[i] < stack[stack.length - 1]){
            stack.pop();
        }
		
        // 돌 명단이 비어있거나, 새로 쌓아야 할 돌이 스택의 마지막 돌 보다 높다면 새로 쌓는다.
        if(stack.length == 0 || H[i] > stack[stack.length - 1]){
            stack.push(H[i]);
            count++;
        }
    }

    return count

}

  • 이전 블록의 높이가 현재 블록의 높이보다 높으면, 현재 블록은 이전 블록과 하나로 합쳐질 수 있으므로, 스택 lastH에서 pop을 시킨다.

  • 스택 lastH가 비어있거나, 이전 블록의 높이보다 현재 블록의 높이가 높으면 별도의 블록 조각이 필요하므로 스택 lastH에 push하고 blocks 카운트를 증가시킨다.



2. Python



def solution(H):
    
    stack = []
    count = 0

    for h in H:

        while stack and stack[-1] > h:
            stack.pop()

        if not stack or stack[-1] < h:
            stack.append(h)
            count += 1
        
    return count


좋은 웹페이지 즐겨찾기