핵심

• 왼쪽에 비어있는 게 없으면, 현재 들어오는 녀석보다 큰것
  • 그러므로 결과값에 1을 더해준다.
• 만약 새로 들어올 사람의 키가 왼쪽보다 크거나 같으면 빼기 시작한다
  • 여기서 중요한 것이 저장한 인원수
  • 키가 같은 사람들이 붙어있으면 그 사람들을 합해서 생각해야한다
• 이부분까지는 빠르게 고려를 했는데, 인원수를 더하는 계산을 정리하지 못함.
  • 동일하거나 키가 작은 사람들을 모두 소거하고나면 왼쪽에 남아있는 것은 키가 큰 사람들이라는 사실을 계속 망각하고 남은 사람들을 모두 고려하려고 하는 실수를 함.
  • 그냥 result+1 해주면 왼쪽 고려 끝남
  • 그림을 그리면서 풀어야겠다.

코드

package Baekjoon;


import java.io.*;
import java.util.*;
public class Algo3015 {

    static int N;
    static int[] cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cnt = new int[N];

        Deque<int[]> st = new ArrayDeque<>(500000);
        long result = 0;
        st.add(new int[]{Integer.parseInt(br.readLine()), 1});

        for(int i=0; i<N-1; i++) {
            int current = Integer.parseInt(br.readLine());
            int cnt = 1;

            //오른쪽에 새로 들어올 사람에 대해서 상대적인 키를 체크한다.
            while(!st.isEmpty() && current>=st.peek()[0]){
                int[] temp = st.pop(); //더 작거나 같으면 뽑고
                result += temp[1]; //그 인원수만큼 더해준다
                if(temp[0]==current) cnt+=temp[1]; //만약 키가 같다면, 다음 새로 들어올 사람도 이에 대한 카운트를 해줘야하므로 더한다.
            }

            //바로 왼쪽에 대해서
            if(!st.isEmpty()) {
                result++;
            }

            st.push(new int[]{current, cnt});
        }


        System.out.println(result);
    }
}