[BOJ/Java] 1863: 스카이라인 쉬운거

문제

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

스카이라인은 건물의 그림자를 말한다.

스카이라인을 보고 도시에 세워진 건물이 몇 채인지 알고싶다.

정확히 몇개인지 아는 것은 대부분 불가능하고, 최소한 몇 채인지 알아내고 싶다. 

아래 스카이라인을 보자.

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

다음 스카이라인에는 최소 6개의 건물이 있다.

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

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

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

 

n개의 건물의 높이가 바뀌는 순간의 (x, y) 좌표가 주어진다. 

• 1 ≤ n  ≤ 50,000
• 1 ≤ x ≤ 1,000,000
• 1 ≤ y ≤ 500,000

 

풀이

 

• 스택을 활용하여 이전 높이 정보를 저장하며, 현재 위치의 높이와 비교해 변화 여부를 판단한다.
• 높이가 0인 경우, 현재 지점은 건물이 없는 공간을 의미하므로
  → 지금까지 유지된 높이(=건물)를 모두 종료시켜
  → 스택에 쌓인 높이 개수만큼 건물을 카운트하고,
  → 스택을 비운다.
• 현재 높이가 이전보다 낮아진 경우,
  → 이전에 이어지던 높은 건물이 끝난 것으로 간주하여
  → 스택에서 높이를 하나씩 제거(pop)하면서 count를 증가시킨다.
  → 현재 높이보다 작거나 같은 높이가 나올 때까지 반복한다.
• 현재 높이가 이전보다 높아진 경우,
  → 새로운 건물의 시작으로 판단하여
  → 현재 높이를 스택에 추가(push)한다.
• 반복이 끝난 후에도 스택에 남아 있는 높이들은 종료되지 않은 건물들이므로
  → 그 수만큼 추가로 count한다.

 

코드

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());
        List<int[]> skylines = 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());
            skylines.add(new int[]{x, y});
        }

        int count = 0;
        Stack<Integer> stack = new Stack<>();
        for (int[] skyline : skylines) {
            if (skyline[1] == 0) {
                count += stack.size();
                stack.clear();
                continue;
            }

            while (!stack.isEmpty() && stack.peek() > skyline[1]) {
                stack.pop();
                count++;
            }

            if (stack.isEmpty() || stack.peek() < skyline[1]) {
                stack.push(skyline[1]);
            }
        }

        System.out.println(count + stack.size());
    }

}