[ BOJ ][JAVA][1863] 스카이라인 쉬운거

www.acmicpc.net/problem/1863

1863번: 스카이라인 쉬운거

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	548	204	158	39.109%

문제

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

입력

첫째 줄에 n이 주어진다. (1≤n≤50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1≤x≤1,000,000. 0≤y≤500,000) 첫 번째 지점의 x좌표는 항상 1이다.

출력

첫 줄에 최소 건물 개수를 출력한다.

예제 입력 1

10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

예제 출력 1

6

코드

*
    스카이라이 쉬운거
- 고도가 변하는 지점들을 모두 체크하면서, Stack 자료구조를 이용한다.
- 고도가 같다면 그대로 가면되고, 고도가 낮다면 건물의 개수가 추가되어야 한다.
*/
import java.io.*;
import java.util.*;
public class p1863 {
    static int n;

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

        int answer = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[i] = b;
        }
        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i <= n; i++) {
            while (!stk.empty() && stk.peek() > arr[i]) {
                answer ++;
                stk.pop();
            }

            if (!stk.empty() && stk.peek() == arr[i]) {
                continue;
            }

            stk.push(arr[i]);
        }
        System.out.println(answer);
    }
}