백준 1863

1863번: 스카이라인 쉬운거

---

문제

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

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

 

입력

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

 

출력

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

 

제한

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

---

문제 풀이 과정

고도가 낮아질 때 건물의 개수를 세주면 된다.

만약 같은 고도이면, 같은 건물으로 취급하므로 push 하지 않는다.

그리고 height 를 N+1 크기로 초기화하면 , 젤 마지막 원소는 0이 들어가게된다.

마지막 원소 0은, 마지막 건물을 셀 때 사용할 수 있다.

---

정답 코드

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

class Main1863 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] height = new int[N + 1];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			height[i] = y;
		}

		int answer = 0;
		Stack<Integer> s = new Stack<>();
		for (int i = 0; i <= N; i++) {
			while (!s.isEmpty() && s.peek() > height[i]) {
				answer++;
				s.pop();
			}

			if (!s.isEmpty() && s.peek() == height[i]) {
				continue;
			}

			s.push(height[i]);
		}

		System.out.println(answer);
	}

}