백준 1863 - 스카이라인 쉬운거 Java

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이다.

출력

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

예제 입력 1

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

예제 출력 1

6

힌트

입력은 다음과 같은 스카이라인을 나타낸다.

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX

다음과 같이 여섯 개의 빌딩이 있을 때가 최소 개수의 빌딩이 있는 상황이다.

..........................
.....22.........333.......
.111.22.......XX333XX.....
X111X22XXX....XX333XXXXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......5555555.....
4444444444....5555555XXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

문제 해설

• 건물의 높이(입력값 중 y)가 달라지는 걸 체크하기 위해 Stack을 사용.
• 건물의 높이가 높아지면 그 뒤에 하나의 건물이 더 있다는 뜻으로 봐도 된다. (Stack에 push해서 y의 높이를 저장)
• 건물의 높이가 낮아지면 뒤에 있는 건물이 끝났다는걸 의미하기 때문에 Stack에서 pop하면서 건물의 개수를 1 늘려준다.
• 현재 Stack에 저장되어 있는 값 중 가장 나중에 들어온 값과, y가 같다면 건물의 높이는 변하지 않은 것이기 때문에 같은 빌딩이라고 봐도 됨.
• 만약 입력을 다 받았는데, stack에 값이 남아있으면, 건물이 남아있는 것과 마찬가지이므로, 남아있는 값의 개수만큼 answer++해주면 됨

package BOJ;

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

public class BJ_1863_스카이라인쉬운거 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int answer = 0;
        Stack<Integer> stack = new Stack<>();

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

            //스택이 비지 않았고, 가장 마지막에 들어온 값보다 y가 클 때,
            //건물 하나를 추가해주고, stack에서 pop을 한다.
            //높이가 낮아졌을 때를 의미, 곧 건물이 하나 더 있다는 뜻, pop을 하는 이유는 ?
            while(!stack.isEmpty() && stack.peek() > y)
            {
                answer++;
                stack.pop();
            }
            //높이가 같다면, 같은 빌딩이라는 뜻이기 때문에 stack에 넣을 필요가 없음
            if(!stack.isEmpty() && stack.peek() == y)
            {
                continue;
            }
            //높이가 높아졌다면 stack에 push해서 최고층 높이의 건물을 갱신
            stack.push(y);
        }
        //만약 스택이 비지 않았다면?
        while (!stack.isEmpty())
        {
            //남은 건물이 있다는 뜻이므로 answer를 ++ 해주고, pop 진행
            if(stack.peek() > 0)
            {
                answer++;
            }
            stack.pop();
        }
        System.out.println(answer);
    }
}