Lesson 7: Stacks and Queues → Stone Wall

문제

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

StoneWall coding task - Learn to Code - Codility

 

---

문제 풀이

각 돌의 높이가 주어지고, 돌담을 구성하기 위한 최소의 돌의 개수를 구하는 문제이다.

stack을 이용하여, stack[-1]의 값이 현재 돌의 높이 보다 낮으면 기준을 현재로 변경한다.

stack[-1]이 현재 돌의 높이보다 높으면 카운트를 증가하고 스택에 추가하고 반대일 경우 높이가 클 때까지 stack.pop() 을 진행한다.

---

코드

def solution(H):
    stack = []
    cnt = 0
    for stone_size in H:
        while len(stack) > 0 and stack[-1] > stone_size:
            stack.pop()
        if not stack or stack[-1] < stone_size:
            stack.append(stone_size)
            cnt += 1
    return cnt