백준 1027 : 고층 건물

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

1027번: 고층 건물

[ 문제풀이 ]

N이 최대 50이기 때문에 모든 빌딩을 빌딩 위치부터 좌측(우측)을 탐색하면서 가장 최근에 구한 고층빌딩의 기울기보다 작은(큰) 빌딩들의 개수를 구해주면 된다.

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

public class Main {
	
	static int N, answer;
	static double[] building;
	static Stack<Double> stack;
	
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			building = new double[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; ++i) {
				building[i] = Double.parseDouble(st.nextToken());
			}
			
			stack = new Stack<>();
			for (int i = 0; i < N; ++i) {
				answer = Math.max(answer, solve(i));
				stack.clear();
			}
			bw.write(answer + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static int solve(int pos) {
		//기준점 좌측
		for (int i = pos - 1; i >= 0; --i) {
			double slope = (building[pos] - building[i]) / (pos - i);
			if (i == pos - 1 || stack.peek() > slope) {
				stack.push(slope);
			}
		}
		
		//기준점 우측
		for (int i = pos + 1; i < N; ++i) {
			double slope = (building[i] - building[pos]) / (i - pos);
			if (i == pos + 1 || stack.peek() < slope) {
				stack.push(slope);
			}
		}
		return stack.size();
	}
}