코테 백준 6198 골드5

백준 6198

배열도 많이 사용했고 코드도 좀 지저분했다. 결론부터 말하자면 결과는 문제없는것 같은데 시간초과라고 나왔다. 아이디어보다는 왜 시간초과가 나왔는지에 중점을 두었다. 자료구조측면에서는 문제가 없지만 조건문을 많이 사용해서 시간초과가 발생한것같다. 그래서 최대한 조건문을 사용하지 않는 방법을 떠올려보자고 느꼈다.

import sys
from collections import deque
input=sys.stdin.readline

n=int(input())
height=[]
stack=[]
answer=[]

for i in range(n):
    height.append(int(input()))
    
height.reverse()

for i in height:
    result=True
    if not stack:
        stack.append(i)
        answer.append(0)
    else:
        cnt=0
        last=deque()
        while stack:
            a=stack.pop()
            if i>a:
                cnt+=1
                last.appendleft(a)
            else:
                answer.append(cnt)
                stack.append(a)
                stack+=last
                result=False
                stack.append(i)
                break
        if result==True:
            answer.append(cnt)
            stack+=last
            stack.append(i)
            
print(sum(answer))

위의 코드는 오답 코드이고 다른분의 아이디어만 참고해서 구현하도록 노력했다.
특정 건물에서 다른 건물이 보이는 갯수가 아닌 특정 건물이 보이는 다른건물들의 갯수를 세자고 아이디어를 세웠다.
개인적으로 생각의 발상이자 내가 이런 생각을 할 수 있을까하지만 해야한다. 노력하면서 기르자.

import sys
input=sys.stdin.readline

height=[]
stack=[]
cnt=0

for i in range(int(input())):
    height.append(int(input()))

for i in height:
    while stack and stack[-1]<=i:
        stack.pop()
    stack.append(i)

    cnt+=len(stack)-1

print(cnt)