태야

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

import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    stack = [] #(높이, 동일 높이 연속 개수) 집합
    result = 0
    for h in heights:
        same_count = 1
        #현재 h보다 작은 사람들은 볼 수 없으므로 pop하고, 그들이 형성헀던 쌍의 수를 더함
        while stack and stack[-1][0] < h:
            result += stack[-1][1]
            stack.pop()

        # 같은 높이의 경우, 같은 높이 그룹의 사람들과는 모두 볼 수 있음
        if stack and stack[-1][0] == h:
            cnt = stack[-1][1]
            stack.pop()
            result += cnt # 같은 높이 사람들과의 쌍 추가

            # 만약 스택에 아직 사람이 남아 있다면, 그 다음 높이 같은 사람과도 볼 수 있음
            if stack:
                result += 1
            same_count = cnt + 1
        else:
            # 스택이 비어있지 않다면, 바로 앞 사람과는 항상 볼 수 있음
            if stack:
                result += 1
        stack.append((h, same_count))
    return result

print(get_answer())

이 알고리즘의 핵심은:

• 왼쪽부터 순회하면서 스택에 (높이, 동일 높이 연속 개수)를 저장한다.
• 현재 사람보다 작은 사람들은 pop하여 그동안 형성된 쌍을 결과에 더하고,
  동일한 높이의 사람들은 하나의 그룹으로 묶어 개수를 관리한다.
• 남아 있는 스택의 최상단이 있다면 그 사람과는 볼 수 있으므로 1을 더한다.

이 방식은 각 사람을 한 번씩만 처리하여 O(N) 시간 내에 해결할 수 있다.