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

📖 문제

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

 

 

 

💡  풀이 방식

• 스택

. 건물의 높이(y)가 달라지는 걸 확인하기 위해 스택을 활용한다.

 

- 건물의 높이가 낮아진 경우           > 뒤에 있는 건물이 끝났다는 의미. 스택이 비지 않을 때까지 한 빌딩과 해당 빌딩과 같은 높이의 빌딩을 같은 빌딩으로 취급하며 제거

- 건물의 높이가 같은 빌딩인 경우  > skip

- 건물의 높이가 높아진 경우           > 스택에 push해 최고층 높이의 건물 갱신

 

 

💥 유의사항

- 입력을 다 받았는데 스택에 값이 남아있다면, 건물이 남아있는 것과 마찬가지이므로 남아있는 값의 갯수만큼 하나의 건물로 취급해 건물 갯수를 센다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int ans = 0;
        Stack<Integer> stack = new Stack<>();   // 건물 높이가 달라지는 걸 확인하고자 Stack 사용
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            // 높이가 낮아지면, 뒤에 있는 건물이 끝났다는 의미
            while(!stack.isEmpty() && stack.peek() > y) {
                ans++;
                stack.pop();
            }
            
            // 높이가 같은 빌딩인 경우 skip
            if(!stack.isEmpty() && stack.peek() == y) {
                continue;
            }
            
            // 높이가 높아진 경우, stack에 push해 최고층 높이의 건물 갱신
            stack.push(y);
        }
        
        // 스택이 비지 않은 경우
        while(!stack.isEmpty()) {
            // 남은 건물이 있는 경우
            if(stack.peek() > 0) {
                ans++;
            }
            stack.pop();
        }
        
        System.out.println(ans);
    }
}

 

 

 

 

➕ 다른 풀이 방식

조금 다르다.

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

---

💦 어려웠던 점

- 스택을 사용할 생각조차 하지 못 했다.ㄴㅇㄱ 2차원 배열 안에 값들을 넣어놓고 직사각형 갯수를 직접 만들어 셀 생각을 했다.ㅋ

 

 

🧐 새로 알게 된 내용

- 스택 활용 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 정답 제출 시 참고한 풀이

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

 

- 풀이가 약간 다르지만 이해할 때 참고한 풀이

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