[Gold IV][JAVA]1863번:스카이라인 쉬운거

[Gold IV]1863번:스카이라인 쉬운거 - 바로가기

힌트

입력은 다음과 같은 스카이라인을 나타낸다.

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX

다음과 같이 여섯 개의 빌딩이 있을 때가 최소 개수의 빌딩이 있는 상황이다.

..........................
.....22.........333.......
.111.22.......XX333XX.....
X111X22XXX....XX333XXXXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......5555555.....
4444444444....5555555XXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

풀이과정

고도가 같다면 그대로 가면되고, 고도가 낮다면 건물의 개수가 추가되어야 한다.
=> 고도가 낮아지면 1개 이상의 건물이 끝났다는 의미

1. 입력값을 받으면서 스택을 이용하여 건물의 높이를 관리합니다.
2. 높이가 감소하는 경우:

• 스택에서 pop을 하면서 이전에 저장된 높이와 비교합니다.
• 높이가 달라졌다면 새로운 건물이 시작된 것으로 간주하고 건물의 개수를 1 증가시킵니다.

3. 높이가 같다면 같은 건물로 간주하고 건물의 개수를 그대로 유지합니다.
4. 입력을 모두 받은 후에도 스택에 값이 남아있다면:
   이는 아직 끝나지 않은 건물을 의미하므로, 해당 개수만큼 건물의 개수를 추가합니다.
   계산된 건물의 개수를 출력합니다.

스택의 변화 과정

[1]
[1, 2]
[1, 3]
[0]
[0, 2]
[0, 2, 3]
[0, 1]

정답

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

public class Main { //유형: 자료구조, 스택 , 메모리제한: 128 MB, 시간 제한: 2초
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine());
        int answer = 0;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            while (!stack.isEmpty() && stack.peek() > y) { // 이전 높이 > 현재 높이를 비교
                answer++;
                stack.pop();
            }
            if (!stack.isEmpty() && stack.peek() == y) { //높이가 같다면
                continue;
            }
            stack.push(y);
        }

        while (!stack.isEmpty()) {
            if (stack.peek() > 0) { // 남은 건물
                answer++;
            }
            stack.pop();
        }
        System.out.println(answer);
    }
}