(코딜리티) Lesson 7. [Stacks and Queues] : StoneWall - python

문제 : app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

StoneWall coding task - Learn to Code - Codility

문제 내용

돌로 된 벽을 만들려고 한다. N미터가 담겨있는 배열 H를 제공할 때, 최소한의 벽돌 갯수를 return하시오. 

I는 벽돌의 위치로 왼쪽에서 시작하여 오른쪽으로 끝이나며, H[I] = 미터이다.

 

예를 들어, H = [8, 8, 5, 7, 9, 8, 7, 4, 8]인 경우,

H[0]과 H[1]은 길이가 같아서 1개의 벽돌만 있어도 된다.

H[2]의 경우 이전의 벽돌보다 더 작기 때문에 1개의 벽돌이 추가 된다.

H[5]까지는 계속 추가 되다가 H[7] = 7로 H[3]의 7과 같아서 벽돌을 추가하지 않아도 된다.

 

위와 같은 과정을 반복하면서 생기는 벽돌은 아래의 이미지와 같다.

 

벽돌은 총 7개가 필요하므로, 7을 return한다.

제한 사항

• N은 1~100,000
• 배열 H의 각 요소는 1~1,000,000,000

코드

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:
            count += 1
            stack.append(h)
        
    return count

해설

진짜 이건 문제 이해를 못해서 검색해봤는데도 이해를 하는데 오래 걸렸습니다... 문제만은 이해가 안되서 결국 알고리즘코드를 보면서 이해를 했네요.. 

 

문제를 이해하면 쉬운 내용이라 위에 제가 이해하고 글로 쓴 것도 보면 쉽게 풀 수 있을 거라 생각이 듭니다.