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

6198. 옥상 정원 꾸미기

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

 

 

• 첫 풀이 - 시간초과
  • 스택을 사용해서 맨 뒤의 값이랑 비교해야하는 건 알았으나
  • 값을 구해오는 과정에서 for문을 2번 돌고 최악의 경우 n^2

n = int(input())
buildings = [int(input()) for _ in range(n)]
buildings.append(int(1e9))


result = []
answer = 0
result.append(buildings[0])

for i in range(1, n+1):
    if result and buildings[i] < result[-1]:
        result.append(buildings[i])
    else:
        for j in range(len(result)-1, -1, -1):
            if buildings[i] > result[j]:
                answer += len(result[:j])
                result.pop()
        result.append(buildings[i])

print(answer)

 

 

• 다른 사람 풀이
  • 스택
  • i번째 건물을 볼 수 있는 건물 수를 더해주는 것
  • i번째 건물을 확인할 때, 이전 값중 작은 애들은 다 지우고 남은 애들만 더함

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

for bd in buildings:
    while stack and stack[-1] <= bd:
        stack.pop()

    answer += len(stack)
    stack.append(bd)

print(answer)