옥상 정원 꾸미기 (6198번) - 백준 (BOJ)

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

 

백준 - 옥상 정원 꾸미기 (Bad Hair Day) (6198번)

 

난이도 : Gold 5

알고리즘&자료구조 : Stack (스택)

 

 

import sys
input = sys.stdin.readline


class Cows():
    def __init__(self):
        self._stack(int(input())-1)
        
    
    def _stack(self, N):
        stack = [int(input())]
        cnt = idx = 0
        for _ in range(N):
            cur = int(input())
            idx += 1
            while stack and stack[-1] <= cur:
                idx -= 1
                stack.pop()
            cnt += idx
            stack.append(cur)
        self.answer = cnt

        
if __name__ == '__main__':
    cow_hairs = Cows()
    print(cow_hairs.answer)

 

 

스택 (Stack) 을 활용하는 문제이다.

 

---

 

▶ 주어진 숫자 리스트에서, 숫자를 하나씩 받아온다.

 

 

▶ 현재 받아온 숫자 ( cur ) 가, 스택에 들어간 가장 최근 숫자 ( stack[-1] ) 보다 작을 때까지

( while stack and stack[-1] <= cur )

스택에서 숫자를 제거해나간다. ( stack.pop() )

 

 

▶ 스택이 비었거나, 스택의 가장 최근 숫자 ( stack[-1] ) 가 현재 숫자 ( cur ) 보다 크다면,

스택에 현재 숫자를 추가해주고 ( stack.append(cur) )

cnt 에 현재 숫자가 추가된 스택의 인덱스 ( idx ) 를 더해준다. ( cnt += idx )

 

 

▶ 모든 숫자를 다 받아서 위의 작업을 거친 뒤,

cnt 값을 반환한다.