백준 1863번 (java) Stack

백준 1863번 스카이라인 쉬운거 java

관찰

예시를 들어보자 (빨간색은 입력 좌표)

이 그림을 보면서 빌딩을 세어보면 규칙이 보인다 정답은 5개

1. 앞에 1,2,3,4번으로 올라가는 수가 있으면 빌딩이 생긴다. 근데 5번이 들어오면 2,3,4번을 채워야 하는 빌딩이 결정된다.

2. 그렇기 때문에 빌딩의 높이보다 작은 수가 들어오면 그 수와 작은 수 사이의 높이인 빌딩들은 해결된다. (2,3,4번)

3. 여기서 1번처럼 초기화 되지 않으면 그냥 기다리고 있다가 끝나면 마지막에 0을 넣으면서 모두 초기화 된다.

결국 핵심은 가장 마지막에 들어온 높이를 계속 비교해줘야 하고 만약에 마지막에 있는 높이를 수정해줘야 한다. -> 후입선출 Stack으로 접근해주자

정답 코드

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

public class Main {
    static int n,answer;
    static Stack<Integer> stack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        answer = 0;
        stack.push(0);
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            int cur = stack.peek();

            if(cur < r){
                stack.push(r);
            }
            else{
                while(true){
                    int tmp = stack.peek();
                    if(tmp <= r){
                        break;
                    }
                    else{
                        answer++;
                        stack.pop();
                    }
                }
                // 새로운 높이를 스택에 추가 0이 아닐 때만
                if(stack.peek() < r){
                    stack.push(r);
                }
            }
        }

        while(true){
            int tmp = stack.peek();
            if(tmp == 0){
                break;
            }
            else{
                answer++;
                stack.pop();
            }
        }

        System.out.println(answer);
    }

}

---

풀이

1. 좌표는 순차적으로 가로와 세로가 들어오는데 가로는 증가하게 계속 들어오므로 처리해 줄 필요가 없고 높이(r)만 사용한다.

2. 만약 높이가 stack의 가장 마지막 부분보다 크다면 그냥 추가한다. (왼쪽 튀어나온 빌딩 해결)

3. 만약 높이가 더 작다면 자신과 같은 숫자가 나올때까지 빌딩을 제거하면서 answer++ 해준다.

4. 그 다음 만약에 스택에 나보다 작은 것이 담겨있으면 r 높이를 추가해준다. (오른쪽 튀어나온 빌딩 해결)

5. 마지막으로 0으로 끝나지 않았을 경우를 해결해준다.

---

마무리

처음에 스택으로 해결하는지 모르고 풀다가 혼나고 알고리즘을 보고 스택인 줄 알았다.. 사실 스택이라고 떠올렸어야 하는 힌트가 있었는데 아직 자료구조와 친해지지 못한 것 같다 꾸준하게 알고리즘 풀어야겠습니다..