[Java/Stack] 정올 1141. 불쾌한 날

JUNGOL

 

풀이

stack을 사용하면 "stack을 한번 거친 소는 다신 들어올 수 없으므로" 넣는거 N번, 빼는거 N-1번 해서 O(N + N - 1번)의 연산만으로 해결이 가능하다.

 

코드

package algorithm.jol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
/**
 * 수행 시간 : 209ms
 * 메모리 : 43.4 MB
 */
public class JOL_1141_불쾌한날 {
    public static void main(String[] args) throws IOException {
        Deque<Integer> st = new ArrayDeque<>();
        long ans = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            while (!st.isEmpty() && st.peek() <= num) {
                st.pop();
            }
            ans += st.size();
            st.push(num);
        }
        System.out.println(ans);
    }
}