[코딩테스트] 백준 - 스카이라운 쉬운거

스카이라운 쉬운거 1863번

시간제한	메모리 제한
2초	128MB

문제

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

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

 

입력

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

 

출력

 

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

 

나의코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    // 스카이라인 쉬운거 - 1863번
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

        int count = 0;

        for(int i=0;i < N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            st.nextToken();

            // 받은 숫자가 이전에 수보다 크면 앞에 건물이
            // 넣어주기
            // 작으면 빼주기

            int height = Integer.parseInt(st.nextToken());

            // 높이가 낮아짐 - 건물이 있음
            // 비어있지 않을경우
            while(!stack.isEmpty() && stack.peek() > height){
                count++;
                stack.pop();
            }

            if(stack.isEmpty() || stack.peek() != height){
                stack.push(height);
            }

        }
        // 다 돌았는데도 스택이 비어있지 않다면? - 건물이 하나 더 있는거니까 pop해서 count 해줌
        while (!stack.isEmpty()){
            if(stack.peek() != 0){
                count++;
            }
            stack.pop();
        }

        System.out.println(count);

    }

}