[BOJ 1863] 스카이라인 쉬운거(Java, Stack)

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

1863번: 스카이라인 쉬운거

1. 주어진 입력에서 y와 높이가 같은 건물은 최소 1개 존재해야 한다.

 

 

 

2. 최소 1개는 존재해야 하는 건물이 최대한 넓은 범위를 커버해야, 최소의 갯수를 찾을 수 있다.

 

 

 

3. 고도가 변하는 지점들을 모두 체크하면서, Stack 자료구조를 이용한다.

* 고도가 같다면 그대로 가면되고, 고도가 낮다면 건물의 개수가 추가되어야 한다.

---

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static Scanner sc;
    static int N, x, y;
    static Vector<Integer> v;
    static int answer = 0;
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sc = new Scanner(System.in);
        
        N = sc.nextInt();
        int[] arr = new int[50002];
        
        for(int i = 0; i < N; i++){
            x = sc.nextInt();
            y = sc.nextInt();
            arr[i] = y;
        }
        
        Stack<Integer> stk = new Stack<Integer>();
        for(int i = 0; i <= N; i++){
            while(!stk.empty() && stk.peek() > arr[i]){
                answer += 1;
                stk.pop();
            }
            
            if(!stk.empty() && stk.peek() == arr[i])
                continue;
                
            stk.push(arr[i]);
        }
        
        System.out.println(answer);
    }
}