문제

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

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 $2^{31}$ 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력
서로 볼 수 있는 쌍의 수를 출력한다.

예제 입력 1
7
2
4
1
2
2
5
1
예제 출력 1
10

접근

그냥 음~ 단조 스택이네~ 이러고 풀기 시작했는데
영원히 $O(N^2)$ 풀이밖에 안 떠올랐다.
그리고 키가 동일한 사람이 연속해서 나올 때는 어떻게 처리해야 할지가 문제였다.
그래서 풀이를 봤는데, 스택에 (키, 해당 키의 연속 등장 횟수) 쌍을 저장하더라.
이 쌍을 (input, count)라고 해보자.

현재 키 input을 처리할 때
1. 스택 꼭대기의 키가 input보다 작은 동안 pop하며 ans += 그 묶음의 count.
2. 꼭대기 키가 input과 같으면 ans += 그 묶음의 count를 수행한다. (새롭게 추가된 사람과 이미 스택에 있던 키가 동일한 사람끼리는 모두 서로 볼 수 있기 때문.)
그리고 그 묶음의 count를 1 늘린다. 그 후, 스택에 그 묶음 아래에 뭐가 더 남아 있다면 (즉, 더 큰 키가 뒤에 있다면) 그 더 큰 키 1명도 더 보이므로 ans++.
3. 꼭대기 키가 input보다 커지면 ans++ 하고 (input,1)을 푸시.

모든 입력 키에 대해 위 과정을 반복하면 된다.
아 뭔가 무슨 얘긴지 알 것 같긴 한데 헷갈린다....

구현

import java.io.*;
import java.util.Stack;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long ans = 0;
        Stack<int[]> stack = new Stack<>(); // (키, 해당 키를 가진 사람이 몇 명 연속해 있는지)
        
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());

            while (!stack.isEmpty() && stack.peek()[0] < input) {
                ans += stack.pop()[1];
            }

            if (stack.isEmpty()) {
                stack.push(new int[] {input, 1});
                continue;
            }
            
            int[] top = stack.peek();
            if (top[0] == input) {
                ans += top[1];
                top[1]++;
                if (stack.size() > 1) {
                    ans++;
                }
            } else {
                ans++;
                stack.push(new int[] {input, 1});
            }
        }

        System.out.println(ans);
    }
}