[Java] 백준 3015번 오아시스 재결합 - Stack

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

3015번: 오아시스 재결합

https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-3015-%EC%9E%90%EB%B0%94-%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4-%EC%9E%AC%EA%B2%B0%ED%95%A9-BOJ-3015-JAVA

백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA)

"문자열 폭발" 문제처럼 스택을 활용하는 문제는 너무 생각해내기 어렵다...

 

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

public class g1_3015 {
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int n;
    static long ans = 0;

    public static void main(String[] args) {
        n = fs.nextInt();
        Stack<pair> st = new Stack<>();
        
        while (n-- > 0){
            int now = fs.nextInt();

            while (!st.isEmpty() && st.peek().num < now){
                ans += st.pop().cnt;
            }

            int temp = 0;
            if (!st.isEmpty() && st.peek().num == now){
                temp = st.pop().cnt;
                ans += temp;
            }

            if (!st.isEmpty()){
                ans++;
            }

            st.add(new pair(now, temp + 1));
        }
        
        pw.println(ans);
        pw.close();
    }

    static class pair{
        int num, cnt;
        public pair(int num, int cnt){
            this.num = num;
            this.cnt = cnt;
        }
    }

    // ----------input function----------

    static void sort(int[] a) {
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a)
            L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++)
            a[i] = L.get(i);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}