백준 1863번 : 스카이라인 쉬운거 (자바)

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

 

문제

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

---

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.

---

출력

첫 줄에 최소 건물 개수를 출력한다.

🔵풀이

건물의 그림자로 건물의 최소 개수를 구하는 문제입니다. 만약 입력이 n이 8이고 x y가 1 2, 2 4, 3 2, 4 4, 5 1, 6 0, 7 4, 8 2 로 주어졌다면 스카이 라인은 아래와 같이 생성됩니다. 그리고 최소 개수는 6개가 됩니다. 이처럼 다음 그림자가 이전 그림자보다 y가 낮다면 건물은 이어지지 않습니다. 이를 stack과 set을 통해서 구현하였습니다.

그림 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.valueOf(br.readLine());
    StringTokenizer stringTokenizer;
    Stack<Integer> stack = new Stack<>();
    Set<Integer> set = new HashSet<>();
    int answer = 0;
    stack.add(0);

    for (int i=0; i<N; i++){
      stringTokenizer = new StringTokenizer(br.readLine());
      int x = Integer.valueOf(stringTokenizer.nextToken());
      int y = Integer.valueOf(stringTokenizer.nextToken());

      if (y==0){
        answer += stackCount(stack);
        stack.clear();
      } else if (stack.peek()>y){
        while (!stack.isEmpty()){
          if (stack.peek()>y){
            set.add(stack.pop());
          }
          else {
            answer+= set.size();
            set.clear();
            break;
          }
        }
      }
      stack.add(y);
    }

    answer+=stackCount(stack);

    System.out.println(answer);
  }
  static <T> int stackCount(Stack<T> stack){
    Set<T> set = new HashSet<>();

    while (!stack.isEmpty()){
      set.add(stack.pop());
    }
    return set.size()-1;
  }
}