[백준][Platinum V] 3015번 : 오아시스 재결합 - JAVA(자바)

[Platinum V] 오아시스 재결합 - 3015

문제 링크

성능 요약

메모리: 57688 KB, 시간: 464 ms

분류

자료 구조, 스택

제출 일자

2023년 10월 14일 20:08:45

문제 설명

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

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

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

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

입력

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

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

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

출력

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

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

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

        // 쌍의 개수
        long count = 0;

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

        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(br.readLine());
            Pair pair = new Pair(tmp, 1);

            // 작다면 pop해주고 같다면 횟수만큼 더해주어야 함
            while (!stack.isEmpty() && stack.peek().height <= tmp) {
                Pair top = stack.pop();
                // 나온 횟수를 더 해줌
                count += top.count;
                // 값이 같다면 볼 수 있는 쌍들의 개수를 더해준다.
                if (top.height == tmp) {
                    pair.count += top.count;
                }
            }

            // 비어있지않다면 top에 있는 것과도 볼 수 있으므로 +1
            if (!stack.empty()) {
                count++;
            }

            stack.push(pair);
        }
        System.out.println(count);
    }

    static class Pair {
        // 높이
        int height;
        // 나온 횟수
        int count;

        Pair(int height, int count) {
            this.height = height;
            this.count = count;
        }
    }
}