[BOJ] 백준 1863. 스카이라인 쉬운거

문제

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

1863번: 스카이라인 쉬운거

---

풀이

스택 자료구조를 활용한 문제입니다.  stack에는 순서대로 들어오는 각 층을 쌓습니다.

 

여기서 조건을 잘 정리해야합니다.

 

 우선, 스택이 비어있거나 stack의 peek이 들어올 y좌표보다 작을 때는 push를 합니다.

 

 만약 peek이 크다면, peek이 y좌표보다 작을때마다 pop을 수행하고 pop 개수는 건물의 개수가 됩니다.

 

그리고 반복문이 끝나면 마지막에 남은 stack에 있는 y좌표의 수는 모두 건물의 개수가 됩니다.

 

주의할 것은 y좌표가 0일때는 stack에 push하는 것이 아닌, stack에 있는 모든 것을 비우고 0은 stack에 push하지 않는 것입니다.

 

 

아래는 소스 코드입니다.

 

---

소스코드

import java.util.Scanner;
import java.util.Stack;

public class B1863_스카이라인쉬운거 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        Stack<Integer> stack = new Stack<>();
        int cnt = 0;
        
        for(int i = 0;i<N;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();

            if(y==0){
                while(!stack.isEmpty()){
                    stack.pop();
                    cnt++;
                }
            }
            else if(stack.isEmpty()) stack.push(y);
            else{
                if(stack.peek()<y){
                    stack.push(y);
                }
                else if(stack.peek()>y){
                    while(!stack.isEmpty()&&stack.peek()>y){
                        stack.pop();
                        cnt++;
                    }
                    if(stack.isEmpty()||stack.peek()<y) stack.push(y);
                }
            }
        }
        if(!stack.isEmpty()){
            while(!stack.isEmpty()){
                stack.pop();
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}