[JAVA] 백준 1863 스카이라인 쉬운거 ㅋ

들어가며..

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

이전에 해결 방법이 떠오르지 않아 넘어갔던 문제를 해답을 읽어보면서 답을 찾아나갔다.

또 스택 문제였고, 내가 스택 문제에 약한지 방식이 잘 떠오르지도 않고 이해도 안되었다.

• 너무 어려움 ㅠ

본론

많은 블로그들에서 왜 이 문제를 그렇게 해결하는지에 대한 답이 없었고 코드를 똑바로 안읽고 따라한다고 시행착오를 거쳤다.

아이디어는 다음과 같다.

설명

1. 입력값으로 들어오는 y를 확인하고 직전의 y값이 현재의 y값보다
   1. 크다면 새로운 건물이라고 추정되기 때문에 stack에 삽입한다.
   2. 작다면 건물이 끝나는 지점이라고 추정되기 때문에 stack에서 값을 pop한다.
      • 이 시점에서 끝나는 지점이라고 추정되는 건물이 없을 때까지 반복해준다.
      • 이 반복이 종료된 후, 건물의 높이가 이전 건물의 높이와 같지 않다면, 스택에 삽입해준다. (새로운 건물!)
   3. 만약 건물의 높이가 같다면 이전의 같은 높이와 같은 건물로 추정되기 때문에 스택에 삽입하지 않고 지나간다.
2. 남은 건물의 높이가 0이 아니라면 카운트해준다. 남아있는 건물들도 카운트를 해야하기 때문!

건물의 높이가 같은 경우, 스택에 삽입하지 않는 이유는 추정되는 최솟값을 구해야하기 때문에 같은 건물로 치부해야 한다.

예제

주어진 예제를 가정으로 한번 살펴보겠다.

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

i = 0 : stack [ 1 ]; c = 0

• 가장 처음 높이 1의 건물이 보인다.

i = 1 : stack [ 1, 2 ]; c = 0

• 이전의 건물보다 높은 건물이기 때문에 스택에 삽입해준다. 즉, 새로운 건물이 보인다.

i = 2 : stack [ 1 ]; c = 1

• 이전의 건물보다 낮은 건물이 보인다. 이 경우, 이전의 높이 2의 건물이 모두 지나갔고 이를 카운트해준다.
• 이때, 2를 제거한 후, 이전에 보이는 건물 높이가 현재 값과 동일하므로, 스택에 삽입하지 않고 지나간다. (같은 건물로 간주)

i = 3 : stack [ 1, 3 ]; c = 1

• 이전의 건물보다 높은 건물이기 때문에 스택에 삽입한다.

i = 4 : stack [ 1 ]; c = 2

• 이전의 건물보다 낮은 건물이면서 같은 높이이기 때문에 스택에 삽입하지 않고 이전의 높이 3의 건물을 pop한다.

i = 5 : stack [ ]; c = 3

• 이전의 건물보다 낮은 높이 0이 보이기 때문에 pop하고 카운트해준다.

i = 6 : stack [ 2 ]; c = 3

• 새로운 건물이 보인다.

i = 7 : stack [ 2, 3 ]; c = 3

• 이전보다 높은 건물이므로, 새로운 건물이 보인다.

i = 8 : stack [ 2 ]; c = 4

• 이전보다 낮은 건물이면서 제거한 후 같은 높이이기 때문에 pop해주고 카운트한 후 삽입하지 않는다.

i = 9 : stack [ 1 ]; c = 5

• 이전보다 낮은 건물이면서 제거한 후 다른 높이이기 때문에 pop해주고 카운트한 후 삽입한다.

남은 1높이의 건물을 카운트해준다.

따라서 정답 c는 6이된다.!

소스코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        int answer = 0;
        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());

            st.nextToken();
            int b = Integer.parseInt(st.nextToken());

            // 이전 높이보다 작다면 건물이 끝나는 지점이라고 추정되기 때문에 stack에서 값을 pop한다.
            while(!stack.isEmpty() && stack.peek() > b){
                stack.pop();
                answer++;
            }
            // 만약 건물의 높이가 같다면 이전의 같은 높이와 같은 건물로 추정되기 때문에 스택에 삽입하지 않고 지나간다.
            if(!stack.isEmpty() && stack.peek() == b) continue;

            // 이전 높이보다 크거나 비어있다면 새로운 건물이라고 추정되기 때문에 stack에 삽입한다.
            stack.push(b);
        }

                // 남은 건물들을 카운트해준다.!
        for(int v : stack){
            if(v == 0) continue;
            answer++;
        }

        System.out.println(answer);



    }
}