백준 1027번 : 고층건물 자바

🧫 문제 분석

 

✔️ 출처

고층건물 골드 4

 

📖 문제

 

핵심

사실상 수학문제라고 봐도 과언이 아니라 생각한다.

기울기의 증감을 따져서 비교하면 되는데

 

 

빌딩중 하나를 기준으로 생각해보자. 

좌측 부분은 기울기가 증가 하는 형태이고

우측 부분은  기울기가 감소하는 형태이다.

 

 대략 이렇게 볼 수 있다. 

 

뒷건물에 대해서는 

기울기 최솟값을 저장하고 

최솟값보다 기울기가 크다면 그 빌딩은 볼 수 없는 빌딩이다.

 

앞 건물에 대해서는

기울기 최대값을 저장하고

최댓값보다 기울기가 작다면 그 빌딩은 볼 수 없는 빌딩이다.

 

 

기울기가 같은 현상

문제에서 A-B 빌딩 선분이 다른 빌딩을 지나거나 접하지 않아야한다 했으므로 기울기가 같으면 그 빌딩은 볼 수 없다. 

 

---

🔅 문제 풀이

import java.io.*;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] buildings = new int[n+1];
  
        for (int i = 1; i <= n; i++) {
            buildings[i] = Integer.parseInt(st.nextToken());
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, countBuildings(buildings, i));

        }

        System.out.println(max);
    }


    private static int countBuildings(int[] arr, int num) {
        double gradient = -1000000001;
        int count = 0;
        // 우측
        for (int j = num + 1; j <arr.length; j++) {
        	// 기울기 구하기
            double m = ((arr[j] - arr[num]) / (j - num));

            // 최댓값보다 크면 볼 수 있는 건물 
            // 최댓값 기울기를 갱신
            if (gradient < m) {
                count++;
                gradient = m;
            }
        }

        // 좌측
        gradient = 1000000001;
        for (int j = num - 1 ; j >= 1; j--) {
            double m = (arr[j] - arr[num]) / (j - num);
            // 최솟값보다 작다면 볼 수 있는 건물
            // 최솟값 기울기를 갱신
            if (gradient > m) {
                count++;
                gradient = m;
            }
        }

        return count;
    }


}

 

---

다른 사람풀이를 보며 다시 만든 로직

    private static int countBuildings(int[] arr, int num) {
        double gradient = 0;
        int count = 0;
        for (int j = num + 1; j <arr.length; j++) {
            double m = (double) (arr[j] - arr[num]) / (j - num);

            if (j == num + 1 || gradient < m) {
                count++;
                gradient = m;
            }
        }


        for (int j = num - 1 ; j >= 1; j--) {
            double m = (double) (arr[j] - arr[num]) / (j - num);

            if (j == num - 1 || gradient > m) {
                count++;
                gradient = m;
            }
        }

        return count;
    }

 

내 코드보다 훨씬 이해하기 쉽고 깔끔한거같다. 

처음 접하는 빌딩은 무조건 보이니까 무조건 +1하고 최댓값, 최솟값을 갱신하는 것이 인상적이다.

 

 

 

 

❗ 오답노트 / 필요한 지식

1. 처음 풀때 for문에 i값을 double로 했는데 왜그랬는지 모르겠다. 
2. (double) int / int  시 double형으로 제대로 연산된다.