1863. 스카이라인 쉬운거

Problem 💻

1863. 스카이라인 쉬운거

 

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

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

---

Approach 1 ⭕

• 스택 (00:32:10)

스택으로 푸는 문제였다.

 

처음에 스택이라 생각 못하고 입력값들을 어떻게 활용할지 고민해봤다. 처음엔 직사각형 좌표를 이용해서 풀려고 했다. 예를 들어 2, 2 다음 5, 1이 나오면 {(2, 2), (4, 1)} 좌표를 가지는 직사각형이 한 개 있는 것으로 보는 식으로 풀려고 했는데 이 방법은 넓이를 구할땐 쓸모있을지 몰라도 갯수를 구하는거라 맞는 알고리즘 같지 않았다.

 

그리고, 두 번째로는 지금의 입력값이 2, 2면 이전 입력값 1, 1보다 크니까 계속 진행하다가 5, 1이 나왔을 때 적어도 높이 2의 직사각형이 하나 있는 것이니 +1 하는 식으로 만들려고 했다. 이때, 스택을 사용하면 쉽게 풀 수 있었는데 스택을 생각하지 못해서 알고리즘 분류를 확인했다.

 

예제를 통해 스택을 어떻게 이용할지 알아보자.

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

/**
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX
**/

 

일단 입력값은 스카이라인의 고도가 바뀌는 순서대로 주어진 것이기 때문에 정렬할 필요는 없다. 그럼 순서대로 스택에 한번 넣어보자.

 

 

(1, 1)의 경우 스카이라인이 시작되는 좌표이고 아직 아무 정보도 없으니 일단 스택에 넣는다.

 

 

(2, 2)의 경우에도 (1, 1)의 스카이라인이 끝나는 지점이 아니며, 새로운 빌딩이 보이는 구간의 시작이므로 스택에 그대로 넣는다.

 

 

(5, 1)의 경우 생각을 좀 해봐야 한다. 일단 (5, 1)이 등장한 순간 고도가 낮아지므로 높이가 1보다 큰 빌딩들은 모두 빌딩의 끝이 정해진다. 현재 예제는 아니지만 아래 그림으로 한번 보자.

. . . .
. . x .
. x x .
x x x x

 

(1, 1)이 주어지고, (2, 2), (3, 3)이 차례대로 주어져 스택에 담겨있으면 (4, 1)의 등장으로 (2, 2)로 시작한 빌딩과 (3, 3)으로 시작한 빌딩은 끝이 정해졌다. 즉, 빌딩의 갯수에 추가해야한다. 그러므로 스택에서 1보다 큰 빌딩들을 모두 제거해주면 (3, 3), (2, 2)가 차례대로 나와 빌딩 갯수는 2개가 된다.

 

다시 해당 예제로 돌아와 여기서는 (2, 2)로 시작한 빌딩이 정해진다. 그러므로 (2, 2)를 빼고 빌딩 갯수(ret++)를 하나 증가시킨다.

이후에 생각해볼 거리가 또 하나 있다. (5, 1)을 스택에 넣어야 할까? 아니면 그냥 버려도 되는 것일까? 이를 위해 넣는다와 넣지 않는다 두 가지 경우를 다 생각해보자.

 

• 넣는다.

 

• 넣지 않는다.

 

간단하게 알아보기 위해 위의 두 경우를 하나의 사진으로 표현하였다. 그림을 보면 알 수 있듯이 넣지 않으면 마지막 (22, 1) 빌딩의 경우 없는 빌딩 취급되어 카운팅에 들어가지 않는다. 이를 위해 마지막이 0이 아닌 경우라면 추가 로직을 실행할 수 있겠지만 넣는 것으로 해결하는 것이 더 편하다.

 

위의 과정을 코드로 표현하기만 하면 정답이다!

---

Solution 💡

public class BOJ_1863 {

    private static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int ret = 0;
        ArrayDeque<Point> skyline = new ArrayDeque<>();
        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());

            if (skyline.isEmpty()) skyline.push(new Point(x, y));
            else {
                Point peek = skyline.peek();
                if (peek.y < y) skyline.push(new Point(x, y));
                else {
                    int tmp = 0;
                    while (!skyline.isEmpty() && skyline.peek().y > y) {
                        Point pop = skyline.pop();
                        if (pop.y != tmp) {
                            ret++;
                            tmp = pop.y;
                        }
                    }
                    if (y != 0) skyline.push(new Point(x, y));
                }
            }
        }

        int tmp = 0;
        while (!skyline.isEmpty()) {
            Point pop = skyline.pop();
            if (pop.y != tmp) {
                ret++;
                tmp = pop.y;
            }
        }
        System.out.println(ret);
    }
}