[코딩테스트] 백준 1863번: 스카인라인 쉬운거

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

Problem 💻

문제

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

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

입력

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

출력

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

 

 

Solution 💡

주어진 입력값을 직접 그려도 되고 문제에 힌트를 통해 직사각형 생성 및 카운팅 규칙을 알아내야 한다.

힌트를 분석하여 얻은 규칙은 다음과 같다. 

 

• 높이가 증가하면 새로운 직사각형이 생성
• 높이가 감소하면 기존의 직사각형이 종료
• 스택을 사용하여 효율적으로 높이를 관리

 

분석과정을 살펴보면 

입력값은 좌표 (x, y) 형식으로 높이변화가 있을때 제공된다. 높이가 증가하면 새로운 직사각형이 생성되며, 감소하면 해당 높이의 직사각형이 종료된다.  종료되므로 그때 카운팅을 진행하면 된다.

 

연속적으로 높이가 증가하거나 하거나 첫 값같이 고정된 값에서 시작하는 높이값은 감소하는 순간이 올때까지 그 값들은 간직하고 있을 자료구조가 필요하다. 스택에 경우 후입선출방식으로 동작하며, 높이가 감소하는 순간에 종료되는 입력값은 최신 값이므로 스택을 활용하면 효율적으로 처리할 수 있다.

 

 

예시를 스택으로 처리하면 다음과 같다. 

좌표: (1, 2) → (2, 3) → (3, 2) → (4, 5) → (5, 1)

스택 상태:
- (1, 2): [2]
- (2, 3): [2, 3]
- (3, 2): [2] (3 종료)
- (4, 5): [2, 5]
- (5, 1): [1] (5, 2 종료)
- 끝: [] (1 종료)

 

단, 여기서 주의 할 점은 빈 스택에 스택에 높이 값이 푸시되어 직사각형이 생성된다는 점과 0이 들어올 경우 높이가 0이므로 직사각형을 카운팅하면 안된다는 것이다.

 

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

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

        Stack<Integer> stack = new Stack<>();
        int buildingCount = 0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

						// 빈 스택이 아니고, 높이가 감소한다면 카운팅을 하고 스택을 팝한다.
            while (!stack.isEmpty() && stack.peek() > y) {
                stack.pop();
                buildingCount++;
            }
						
						// 스택이 비었거나 높이가 증가하면 스택에 푸시한다.
            while (stack.isEmpty() || stack.peek() < y) {
                stack.push(y);
            }
        }

        while (!stack.isEmpty()) {
			      // 0의 경우 높이가 0이므로 직사각형으로 카운팅되지 않는다.
			      // 빈스택에 0값이 들어오는 경우가 있을 수 있다.
            if (stack.pop() > 0) {
                buildingCount++;
            }
        }

        System.out.println(buildingCount);
    }
}