백준 3015 (오아시스 재결합) - java

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

3015번: 오아시스 재결합

 

문제 

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

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

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

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

 

유형 : Monotone Stack

 

접근 방식

• 3가지 경우를 고려하면 되는 문제이다.
  • Stack의 peek과 현재의 높이가 같은 경우
  • Stack의 peek보다 현재의 높이가 높은 경우
  • Stack의 peek보다 현재의 높이가 낮은 경우
• 높이가 높은 경우
  • stack에 있는 탑을 볼 수 있다. and pop
• 높이가 같은 경우
  • 볼 수 있다. + 중복 추가
• 높이가 낮은 경우
  • 해당 탑만 볼 수 있다. + 탐색 종료

전체 코드

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

public class Main {

    static int[] board;

    static int[] result;

    static int[] duplicated;
    static int n = 0;

    static long count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        board = new int[n+1];
        result = new int[n+1];
        duplicated = new int[n+1]; // 해당 숫자가 중복으로 나타나는 경우 중복 숫자

        for(int i=1;i<=n;i++){
            board[i] = Integer.parseInt(br.readLine());
        }

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

        for(int i=1;i<=n;i++){

            int tmpCount = 0;

            while(!stack.isEmpty()){
                // 전의 탑보다 큰 경우
                if(board[stack.peek()] < board[i]){
                    count += duplicated[stack.peek()] + 1;
                    tmpCount += duplicated[stack.peek()] + 1;
                    stack.pop();
                }else if(board[stack.peek()] == board[i]){
                    // 값이 같은 경우 중복 처리 필요
                    duplicated[i] += duplicated[stack.peek()] + 1;
                    count += duplicated[stack.peek()] + 1;
                    stack.pop();
                } else{
                    // 작은 경우
                    count++;
                    break;
                }
            }

            stack.push(i);
        }

        System.out.println(count);

        br.close();
    }
}