https://www.acmicpc.net/problem/1863
처음 문제를 봤을 때 그래프를 그리고 그래프를 이용해서 건물을 찾을까 했는데
입력으로 좌표를 전부 준게 아니라 바뀐 위치 좌표만 줬기 때문에
이걸 그대로 이용해서 문제를 풀 수 있지않을까 생각했다.
그러면서 자연스럽게 스택이 떠올랐고
스택에 높이를 오름차순으로 쌓고 숫자가 들어왔을 때 경우를 나눠서 풀면 될 거라고 생각했다.
입력에서 주어진 x좌표는 사용하지 않았다.
stack
: 건물의 높이를 오름차순으로 저장하는 스택
height[]
: 입력받은 건물의 높이를 저장하는 배열
ans
: 건물의 개수, 스택에서 빠져나갈 때 마다 증가
push
ans++
push
continue
ans++
push
ans++
package baekjoon._1863;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static int n;
static int[] height;
public static void input() {
FastReader fr = new FastReader();
n = fr.nextInt();
height = new int[n];
for (int i = 0; i < n; i++) {
int x = fr.nextInt();
height[i] = fr.nextInt();
}
}
public static void main(String[] args) {
input();
pro();
}
public static void pro() {
int ans = 0;
Stack<Integer> stack = new Stack<>();
for (int h : height) {
// 0을 저장하면 안되므로 스택을 비움
if (h == 0) {
ans += stack.size();
stack.clear();
}
else if (!stack.isEmpty()) {
int peek = stack.peek();
// 높이가 높아지면 스택에 push
if (peek < h) {
stack.push(h);
} else {
// 높이가 낮아지면 그 높이보다 높은 건물들은 스택에서 꺼냄
while (!stack.isEmpty() && stack.peek() > h) {
stack.pop();
ans++;
}
// 스택에 없는 새로운 높이라면 push
if(!stack.isEmpty() && stack.peek() < h) stack.push(h);
if(stack.isEmpty()) stack.push(h);
}
} else {
// 스택이 비어있으면 무조건 push
stack.push(h);
}
}
ans += stack.size();
stack.clear();
System.out.println(ans);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}
String next(){
while(st == null || !st.hasMoreTokens()){
try{
st = new StringTokenizer(br.readLine());
} catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
Double nextDouble() { return Double.parseDouble(next()); }
String nextLine(){
String str = "";
try{
str = br.readLine();
} catch(IOException e){
e.printStackTrace();
}
return str;
}
}
}
참고하지않고 스스로 빠르게 풀어서 기분좋은 문제였다.