백준 1863 - 스카이 라인 쉬운거

문제

1863번: 스카이라인 쉬운거

풀이

• 현재까지의 건물 높이값보다 낮은 높이가 들어올 경우 무조건 스카이라인이 바뀐다.
• 따라서 낮은 높이가 들어올 경우

  • 스택이 비지 않을 때까지 한 빌딩과 해당 빌딩과 같은 높이의 빌딩을 같은 빌딩으로 취급하며 제거

  • 높이가 0인 경우는 빌딩으로 취급하지 않으므로 카운팅하지 않음

    이후 들어온 빌딩 높이를 저장

• $n$개의 입력에 대한 처리후, 스택내에 남아있는 빌딩 높이는 전부 같거나, 오름차순의 형태로 형성된다.(스택의 peek 에 있는 높이보다 입력 높이가 작을 경우 스택에서 전부 제거했기 때문에 내림차순의 형태가 절대 나올 수 없다)
• 따라서 남아있는 스택에 있는 빌딩들을 높이에 따라 구분지으며 추가로 카운팅해준다.
  • 이 때도 높이가 0인 경우는 카운팅하지 않는다.

$n$번의 입력을 처리하며 스택에서 더 높은 빌딩을 제하는 연산은 결국 $O(n)$에 수렴한다고 볼 수 있다. 따라서 로직의 전체 시간복잡도는 $O(n)$의 형태를 띄며 이는 $n=50,000$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

예시 과정 - 그림

코드

import static java.lang.Integer.parseInt;

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 = parseInt(br.readLine());
        Stack<Point> stack = new Stack<>();
        int ans = 0;

        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = parseInt(st.nextToken());
            int y = parseInt(st.nextToken());

            while (!stack.isEmpty() && stack.peek().y > y) {
                Point temp = stack.pop();
                if (!stack.isEmpty() && stack.peek().y == temp.y) {
                    continue;
                }
                if (temp.y == 0) {
                    continue;
                }
                ans++;
            }

            stack.push(new Point(x, y));
        }

        while (!stack.isEmpty()) {
            Point temp = stack.pop();
            if (!stack.isEmpty() && stack.peek().y == temp.y) {
                continue;
            }
            if (temp.y == 0) {
                continue;
            }
            ans++;
        }

        System.out.println(ans);
    }

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}