[알고리즘] StoneWall

• StoneWall

def solution(H)

that, given an array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it. For example, given array H containing N = 9 integers: 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 the function should return 7. The figure shows one possible arrangement of seven blocks.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array H is an integer within the range [1..1,000,000,000].

---

이 문제는 뭐지? 싶도록 잘 이해가 안되는 문제였다.

그래서 어떻게 풀까 하다가 너무 간단히라도 풀고 제출했으나 역시 아니었다.

예시는 통과했다고..

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

# stone wall
# N 미터 long, 상수 thickness
# H 높이

# H[0] -> 맨 왼쪽 높이(시작)
# H[7] -> 7+1번째 높이 
# 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개

# 이를 조립하기 위한 최소한의 블록 개수를 구하기.
def solution(H):
    N = 0
    # 높이가 변하는 횟수만 세면 되나.
    for i in range(len(H)-1):
        if H[i] != H[i+1]:
            N += 1
    return N

---

문제풀이

파이썬 풀이 O(N)

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

    for h in H:
        # 현재 높이보다 높은 블록들은 여기서 종료
        while stack and stack[-1] > h:
            stack.pop()

        # 같은 높이면 연장, 더 낮으면 위에서 다 pop되어 있음
        if not stack or stack[-1] = 1 이지만, 안전하게 0은 건너뜀)
            if h > 0:
                stack.append(h)
                blocks += 1
        # stack[-1] == h 면 아무 것도 안 함 (연장)

    return blocks