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

1. 문제분석

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

1863번: 스카이라인 쉬운거

스카이라인은 태양이 질 때에 보이는 건물들의 윤곽이라고 한다.

이때 건물의 최소 개수를 구하는 문제다.

힌트를 보면 이해하기가 쉬워진다. 스카이라인의 고도가 높아졌다가 낮아질때 그 건물의 개수가 특정된다.

고도를 처음부터 보면 1 2 2 2 1 3 3 1 이다. 2 2 2에서 1로 낮아졌을 때 2 2 2는 한 건물로 특정지을 수 있는 것이다.

2. 구현

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

public class Main {

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

        for(int i = 0; i<size; i++){
            String[] info = br.readLine().split(" ");
            arr[i] = Integer.parseInt(info[1]);
        }

        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i<=size; i++){
            while (!stack.isEmpty() && stack.peek() > arr[i]){
                answer++;
                stack.pop();
            }
            if(!stack.isEmpty() && stack.peek() == arr[i]){
                continue;
            }
            stack.push(arr[i]);
        }
        System.out.println(answer);
    }
}

위에서 말한대로 생각한대로 구현해보자.

최고 고도에서 낮아지는 경우를 찾아야하니 스택을 사용했다.

현재 고도가 더 낮다면 그 고도의 높이보다 큰 값들은 모두 건물이라고 특정 지을 수 있는 것이다.

3. 마무리

진짜 문제 이해하는데 1시간 걸렸다. 힌트봐도 이해가 안갔는데 직접 그려보니 이해할 수 있었다.

스카이라인이 진짜 뭔지 몰라서 검색해보기도 했다..