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

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

 

이 문제를 보고 처음엔 건물의 높이가 낮아지고 높아지는것에 분기처리를 하여서 높아질때는 무조건 +1이고 낮아질때는 0 이후로 나온 높이의 최소값보다 작은경우에만 +1을 해주는 방식으로 풀으려 했으나 반례가 생각보다 많이 존재하였다.

 

그래서 GPT 를 이용하여 풀이 방법을 보고 다시 풀었다.

 

다음은 GPT 를 이용한 이 문제의 접근 사고 흐름이다.

 

이 문제에서 진짜로 세는 게 뭔지부터 정리

문제에서 묻는 건
👉 스카이라인에서 서로 다른 ‘건물(높이 구간)’의 개수

여기서 “건물 1개”의 정의를 이렇게 바꿔 생각하면 훨씬 쉬워져:

어떤 높이 h가 시작됐다가, 그보다 낮아지는 순간까지 유지되는 ‘연속 구간’

즉,

• 올라갈 때 → “건물 시작”
• 내려갈 때 → “건물 종료”

이 두 이벤트만 정확히 잡으면 끝이야.

---

“내려갈 때”가 어려운 이유

올라가는 건 쉬워:

• 이전보다 높아짐 → 무조건 새 건물 시작

근데 내려갈 때는?

 

10 → 7 → 5 → 3

이 한 번의 하강에서

• 10도 끝
• 7도 끝
• 5도 끝
  👉 여러 건물이 동시에 끝날 수 있음

그래서 단순히

• “내려갔다” = +1
  같은 로직은 절대 안 맞아.

👉 “얼마나 많은 높이가 끝났는지”를 알아야 함

---

그럼 뭘 기억하고 있어야 할까?

현재 시점에서 필요한 정보는 딱 하나야:

“아직 끝나지 않고 살아있는 높이들”

그리고 그 높이들은 항상 이런 성질을 가짐:

• 아래 → 위로 갈수록 점점 커짐
• 내려가면 큰 것부터 차례대로 사라짐

이 구조를 그대로 말로 쓰면:

“항상 오름차순으로 쌓여 있고,
내려가면 위에서부터 제거된다”

이게 바로 스택의 동작이랑 1:1로 일치해.

 

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

public class Main {
    public static int n, ans;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        ans = 0;
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            int h = Integer.parseInt(st.nextToken());

            while(!stack.isEmpty() && stack.peek() > h){
                int popped = stack.pop();
                if(popped != 0) ans++;
            }

            if(stack.isEmpty() || stack.peek() < h){
                stack.push(h);
            }
        }

        while(!stack.isEmpty()){
            int popped = stack.pop();
            if(popped != 0) ans++;
        }

        System.out.println(ans);

    }
}

 

어렵다 오랜만에 푸니까  그리고 이 코드를 피드백을 했더니 stack은 오래된 자료구조라 보통 코테에서는 스택 대신해서 Deque를 많이 사용한다고 한다.

 

그래서 다시 코드를 고쳐보았다.

 

import java.io.*;
import java.sql.Array;
import java.util.*;

public class Main {
    public static int n, ans;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            int h = Integer.parseInt(st.nextToken());

            while(!stack.isEmpty() && stack.peekLast() > h){
                int popped = stack.pollLast();
                if(popped != 0) ans++;
            }

            if(stack.isEmpty() || stack.peekLast() < h){
                stack.offerLast(h);
            }
        }

        while(!stack.isEmpty()){
            int popped = stack.pollLast();
            if(popped != 0) ans++;
        }

        System.out.println(ans);

    }
}

 

결과적으로 시간은 한 5%정도 감소한거같다.