📙[Algo] BOJ1863. 스카이라인 쉬운거

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

문제 요약

• 주어진 스카이라인 정보를 보고 건물이 최소 몇 채인지 알아내라

시간 제한

• 2초

입력

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

출력

• 첫 줄에 최소 건물 개수를 출력

접근법

• 스택이 오름차순 스택을 유지하도록 담기
  • 만약 다음에 올 원소가 스택의 상단에 있는 값보다 작거나 같다면, pop시도
    • 이때, 카운트는 다음 원소보다 큰 원소를 pop할 때만 카운트
• 마지막에 스택이 비어있지 않다면, 남은 높이가 0보다 큰 원소개수만큼만 추가로 카운트

코드

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

public class Main {

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

        int x, y, cnt = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            while (!stack.isEmpty() && stack.peek() >= y) {
                if (stack.pop() > y) cnt++;
            }

            stack.push(y);
        }

        while (!stack.isEmpty()) {
            if (stack.pop() > 0) cnt++;
        }

        System.out.println(cnt);
    }
}