백준 6198 옥상정원

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

6198번: 옥상 정원 꾸미기

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

 

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)출

출력

각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

 

 

• 예제 입력 1 6 10 3 7 4 12 2
• 예제 출력 1 5

# https://www.acmicpc.net/problem/6198
# 옥상정원 꾸미기 
from collections import deque
import sys 

def solution(number):
	if (len(number) == 1):
		return (0)
	stack = deque()
	sumup = 0
	for i in range(len(number)):
		while (stack and stack[-1] <= number[i]):
			stack.pop()
		stack.append(number[i])
		sumup += len(stack) - 1
	return (sumup)
	

n = int(sys.stdin.readline())
lst = []
for i in range(n):
	tmp = int(sys.stdin.readline())
	lst.append(tmp)
print(solution(lst))


# def solution1(number):
# 	if (len(number) == 1):
# 		return (0)
# 	max = number[-1]
# 	sumup = 0
# 	lenn = len(number)
# 	for i in range(lenn - 2, -1, -1):
# 		if (max < number[i]):
# 			sumup += lenn - i - 1
# 			max = number[i]
# 		else : 
# 			for k in range(i + 1, lenn):
# 				if number[k] >= number[i]:
# 					break 
# 				else : 
# 					sumup += 1
# 	return (sumup)

처음에 for문 두개 돌렸는데 

시간 초과남 

그래서 찾아보니 stack 으로 푸는 문제더라... 

 

지금까지 있는 큰 수를 앞으로 나아가면서 카운팅하는 전략 좋습니다...