[백준] 6198번. 옥상 정원 꾸미기

[백준] 6198번. 옥상 정원 꾸미기 바로가기

아이디어

• 저번에 풀었던 탑의 아이디어 처럼 풀었는데 안 되서 답봤다.. 🥲
• 아직 스택에 대해서 잘 모르고 있는 것 같다 ⭐
• 찾아보니 이렇게 푸는게 monotone stack이라는 알고리즘이었다.

  1. for문을 돌면서 자기 자신을 볼 수 있는 빌딩의 개수를 센다.
     1-1. stack에 자기 자신을 넣는다.
     1-2. stack의 마지막 빌딩이 자기보다 작으면 빼준다.
     1-3. 현재 빌딩보다 큰 빌딩이 나올 때까지 2~3번 반복
  2. stack에 자기 자신을 넣는다.
  3. stack의 길이 - 1(자기자신)이 자신을 볼 수 있는 빌딩의 개수이다.

  stack	현재 빌딩	현재 빌딩을 볼 수 있는 빌딩 개수	빌딩 리스트
  [10]	10	0	[3, 7, 4, 12, 2]
  [10, 3]	3	1(10)	[7, 4, 12, 2]
  [10, 7]	7	1(10)	[12, 2]
  [10, 7, 4]	4	2(10, 7)	[12, 2]
  [12]	12	0	[2]
  [12, 2]	2	1(12)	[]

시간 복잡도

• O(N)

코드

import sys
input = sys.stdin.readline

n = int(input())
buildings = [int(input()) for _ in range(n)]
stack = []
check = 0

for building in buildings:

    # 자신을 볼 수 없는 자신보다 같거나 작으면 stack에서 빼준다.
    while stack and stack[-1] <= building:
        stack.pop()
    
    # stack에 자기 자신을 넣는다
    stack.append(building)
    
    # 자기자신을 볼 수 있는 빌딩 개수
    check += len(stack) - 1 # 자기 자신은 빼준다.

print(check)