백준 3015번 : 오아시스 재결합 Java

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

3015번: 오아시스 재결합

스택을 이용하고

Pair<숫자, 같은 것의 개수> 를 만들어내야 쉽게 풀 수 있는 문제

import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;

class Pair {
    int num;
    int cnt;

    Pair(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Stack<Pair> stk = new Stack<>();

        int firstNum = sc.nextInt();
        stk.add(new Pair(firstNum, 1));

        long ans = 0;

        for (int i = 1; i < N; i++) {
            int cur = sc.nextInt();

            while (!stk.isEmpty() && cur > stk.peek().num) {
                ans += stk.pop().cnt;
            }

            if (stk.isEmpty()) {
                stk.add(new Pair(cur, 1));
                continue;
            }

            if (stk.peek().num > cur) {
                ans++;
                stk.add(new Pair(cur, 1));
            } else if (stk.peek().num == cur) {
                int sameCnt = stk.pop().cnt;
                ans += sameCnt;

                if (!stk.isEmpty()) {
                    ans++;
                }
                stk.add(new Pair(cur, sameCnt + 1));
            }
        }
        System.out.println(ans);
    }
}