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

문제

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

1863번: 스카이라인 쉬운거

 

 

풀이 과정

큰 건물에는 가려질 수 있지만, 작은 건물에는 가려질 수 없다. 따라서 stack을 이용해서 자신보다 큰 값은 pop으로 꺼내면서 건물의 개수를 카운트했다.

그리고 Stack에 값을 넣을 때는 stack의 top에 이미 같은 값이 있다면, 같은 건물일 가능성이 있으므로 넘어갔다.

마지막으로 stack에 오름차순으로 모두 다른 값이 남아있을 수 있으므로 stack의 크기만큼 결괏값에 더해주면 된다.

처음부터 이 부분을 고려하지 않아서 틀렸었다ㅠ 이번에 틀렸으니까 다음엔 안틀려야지..!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

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

        height.push(500001);
        while(N-- > 0){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            while(!height.isEmpty() && height.peek() > y){
                height.pop();
                result++;
            }
            if(y==0) continue;
            if(height.isEmpty() || height.peek()!=y){
                height.push(y);
            }
        }
        result+=height.size();
        System.out.println(result-1);
    }
}

 

 

결과