[BOJ] 백준 1027 - 고층 건물 풀이

1.  문제

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

1027번: 고층 건물

2. 문제 Point

<Error Point>

• 처음 빌딩 높이라는 부분을 받았을 때 기준점이 되는 빌딩을 스택에 넣고 기준점부터 왼쪽, 오른쪽으로 탐색하여 기준점보다 높이가 크거나 같아질 때까지 스택에 넣고 큰 값이 나오면 스택이 비어질 때까지 꺼내면서 카운트를 하는 방식을 생각함 → 이는 예제 입력 3과 같이 높이가 모두 같은 경우 해결이 안됨… (문제에서 주어진 x 좌표를 배제해버린 것이 됨

<풀이 Point>

• 기울기를 알아냄
• 주어진 입력을 받고 순서대로 그 입력의 왼쪽, 오른쪽을 탐색함
• 탐색은 f(x) = ax + b라는 1차함수를 만들고 main에서 탐색하는 점과 함수를 만드려고 탐색하는 점 사이에 있는 점 중 높이가 f(x)에 대입했을 대의 값보다 크거나 같은 점이 하나라도 있다면 함수를 만드려고 탐색하는 점은 main에서 탐색하는 빌딩이 볼 수 없음

3. Code

package brute_force;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class HighBuilding {
    static class Point {
        int x;
        long y;

        public Point(int x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    static List<Point> buildingPointList;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        buildingPointList = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            buildingPointList.add(new Point(i + 1, Integer.parseInt(st.nextToken())));
        }

        // 리스트를 하나씩 돌면서 기준점 객체의 인덱스를 넘겨줌
        for (int i = 0; i < N; i++) {
            max = Math.max(max, (leftCnt(i) + rightCnt(i)));
        }

        bw.write(Integer.toString(max));
        bw.flush();
        bw.close();
        br.close();
    }

    // 왼쪽 탐색
    private static int leftCnt(int idx) {
        // 기준점 1
        Point p1 = buildingPointList.get(idx);
        int cnt = 0;

        for (int i = 0; i < idx; i++) {
            // 기준점 2
            Point p2 = buildingPointList.get(i);

            // 1차함수 만들기 : f(x) = ax + b;
            double a = (double) (p1.y - p2.y) / (p1.x - p2.x);
            double b = (double) p1.y - (a * p1.x);

            // 기준점 1과 기준점 2로 만든 함수의 y값 보다 그 사이에 있는 빌딩들의 높이 값이 작다면 기준점 2는 볼 수 있는 건물
            boolean flag = true;
            for (int j = i + 1; j <= idx - 1; j++) {
                if (a * buildingPointList.get(j).x + b <= buildingPointList.get(j).y) {
                    flag = false;
                    break;
                }
            }
						// flag가 참이라는 얘기는 기준점들 사이에 점들의 높이가 함수값보다 작다는 것!!
            if(flag) {
                cnt += 1;
            }
        }
        return cnt;
    }

    // 오른쪽 탐색
    private static int rightCnt(int idx) {
        // 기준점 1
        Point p1 = buildingPointList.get(idx);
        int cnt = 0;

        for (int i = idx + 1; i < buildingPointList.size(); i++) {
            // 기준점 2
            Point p2 = buildingPointList.get(i);

            // 1차함수 만들기 : f(x) = ax + b;
            double a = (double) (p1.y - p2.y) / (p1.x - p2.x);
            double b = (double) p1.y - (a * p1.x);

            // 기준점 1과 기준점 2로 만든 함수의 y값 보다 그 사이에 있는 빌딩들의 높이 값이 작다면 기준점 2는 볼 수 있는 건물
            boolean flag = true;
            for (int j = idx + 1; j <= i - 1; j++) {
                if (a * buildingPointList.get(j).x + b <= buildingPointList.get(j).y) {
                    flag = false;
                    break;
                }
            }
						// flag가 참이라는 얘기는 기준점들 사이에 점들의 높이가 함수값보다 작다는 것!!
            if(flag) {
                cnt += 1;
            }
        }
        return cnt;
    }
}

4. 배운점

1. 빌딩 및 높이가 주어지는 문제가 나온다고 스택만을 고집하지 말자.
2. 점들이 주어진다면 기울기 및 함수를 의심해보자
3. 기울기는 무조건 실수형!!