[백준_1863번] 스카이라인 쉬운거

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

1863번: 스카이라인 쉬운거

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1863 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		Stack<Integer> stack=new Stack<>();
		int[] height=new int[50002];
		
		int n=sc.nextInt();
		
		for(int i=0;i<n;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			
			height[i]=y;
		}
		
		int result=0;
		for(int i=0;i<=n;i++) {
			/*
			 * i 위치에서 고도가 낮아지면 height[i] 보다 큰 높이들 모두 삭제
			 * 건물 개수 증가
			 */
			while(!stack.isEmpty()&&stack.peek()>height[i]) {
				result++;
				stack.pop();
			}
			
			// 고도가 같다면 넘어가기
			if(!stack.isEmpty()&&stack.peek()==height[i])
				continue;
			
			// 값 추가
			stack.add(height[i]);
		}
		
		System.out.println(result);
	}
}

 

[고찰]

 문제를 몇번을 읽어봐도 문제 자체가 이해가 가지 않아 다른 사람의 포스팅을 참고했다. 코드로만은 이해가 잘 가지 않아 문제의 밑 결과 그림에 집중하니 그릴 수 있는 모든 직사각형을 찾는 것과 같은 문제라는 것을 알았다. 무엇을 구해야 하는지 알고 나니 코드가 이해가 갔지만 스스로 푼 문제가 아니기 때문에 다음에 다시 한 번 풀어봐야겠다.