[백준 1863] 스카이라인 쉬운거 (JAVA)

 

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

1863번: 스카이라인 쉬운거

골드 4문제로, 스택을 사용하여 문제를 풀 수 있다!

예를 들어 

1 1 

2 2

3 3

4 1

일 경우, 

앞에 있는 높이들이 현재 높이보다 크다면 

건물이 있는 것이기에 

스택에 1 ,2 ,3 을 넣고  1이 들어올 차례에

while문을 돌려서 앞에 있는 높이들 중에 1보다 큰 높이가 있는지 확인한다.

크다면, stack.pop을 하여 count+1을 한다!

그리고 포인트로는 1도 건물이기에 

별도로 while문을 돌려서 스택에 0보다 높은 것들이 있는지 확인한다.

 

+ 예시 추가 +

1 2

2 3

3 4

이렇게 있다면, 스택에는 2,3,4가 들어가고 포문이 끝난다.

그럼 별도로 while문을 돌려서 스택에 0보다 높은 것들이 있는지 확인하여 pop and count++ 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		Stack<Integer> s = new Stack<>();
		int count=0;
		StringTokenizer st;
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int idx=Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());
			while(!s.isEmpty()&&s.peek()>h) {
				count++;
				s.pop();
			}
			if(!s.isEmpty()&&s.peek()==h) {
				continue;
			}
			s.push(h);
		}
		
		while(!s.isEmpty()&&s.peek()>0) {count++; s.pop();}
		System.out.println(count);
	}
}