[백 준 Java] 1027번 문제 : 고층 건물

문제 설명

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 문제의 정답을 출력한다.

 

알고리즘

• 수학
• 브루트포스 알고리즘
• 기하학

푼 방법

이 문제를 2차원 좌표계로 생각하면, 건물의 옥상의 좌표를 (건물의 번째 수, 건물의 높이)로 볼 수 있다.

따라서 클래서 Point를 만들어 건물 옥상의 좌표들을 생성하고, 배열에 저장한다.

기준 건물을 정하고, 기준 건물로부터 좌 우의 건물의 선분을 하나하나 생성해서 건물을 볼 수 있는지 비교한다.

 

풀이코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

public class Main {
    List<Point> points; // 점 리스트
    List<List<Segment>> segmentsList; // 선분 리스트
    List<Integer> answers = new ArrayList<Integer>(); // 보이는 건물 갯수를 저장하는 리스트

    public static void main(String[] args) throws IOException {
        List<Double> buildings = new ArrayList<Double>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        double n = Double.parseDouble(st.nextToken());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            buildings.add(Double.parseDouble(st.nextToken()));
        }
        Main main = new Main(buildings);
    }

    Main(List<Double> buildings) {
        if (buildings.size() == 1) { // 건물이 1개일 경우
            System.out.println(0);
        } else if (buildings.size() == 2) { // 건물이 2개일 경우
            System.out.println(1);
        } else {
            points = new ArrayList<Point>();
            // 점 객체 생성 후 점 리스트에 추가
            for (int i = 0; i < buildings.size(); i++) {
                Point p = new Point(i, buildings.get(i));
                points.add(p);
            }

            for (int i = 0; i < points.size(); i++) {
                Point standardPoint = points.get(i); // 기준 점
                int seeCount = 0; // 보이는 건물 수
                // 기준 점으로부터 왼쪽의 건물들이 보이는지 판별
                for (int li = 0; li <= i - 1; li++) {
                    Point viewPoint = points.get(li); // 기준 점에서 볼 건물
                    Segment segment = standardPoint.makeSegment(viewPoint); // 기준점과 볼 건물을 연결한 선분
                    Line line = segment.makeLine(); // 선분을 확장
                    boolean isSeek = true;
                    for (int point = i - 1; point >= li; point--) {
                        Point comparePoint = points.get(point);
                        if (line.isCrossing(line.lineCrossDot(comparePoint.x), comparePoint.y) && li != point) {
                            isSeek = false;
                        }
                        if (li == point && isSeek) {
                            seeCount++;
                        }
                    }
                }
                // 기준 점으로부터 오른쪽의 건물들이 보이는지 판별
                for (int ri = points.size() - 1; ri >= i; ri--) {
                    Point viewPoint = points.get(ri);
                    Segment segment = standardPoint.makeSegment(viewPoint);
                    Line line = segment.makeLine();
                    boolean isSeek = true;
                    for (int point = i + 1; point <= ri; point++) {
                        Point comparePoint = points.get(point);
                        if (line.isCrossing(line.lineCrossDot(comparePoint.x), comparePoint.y) && ri != point) {
                            isSeek = false;
                        }
                        if (ri == point && isSeek) {
                            seeCount++;
                        }
                    }
                }

                answers.add(seeCount);
            }

            System.out.println(Collections.max(answers));
        }
    }

    public class Point {
        double x;
        double y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public Segment makeSegment(Point p1) {
            return new Segment(this, p1);
        }
    }

    /*
     * 선분을 정의한 클래스
     * 구성
     *   변수 : 점, 점
     *   함수 : 직선의 방정식 생성
     */
    public class Segment {
        private final Point p1;
        private final Point p2;
        Segment(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;
        }

        /*
         * 직선의 방정식을 만드는 함수
         * 반환값 : 직선(Line)
         */
        public Line makeLine() {
            double slope = (this.p2.y - this.p1.y) / (this.p2.x - this.p1.x);
            double intercept = this.p1.y - slope * this.p1.x;
            return new Line(slope, intercept);
        }
    }

    /*
     * 직선을 정의한 클래스
     * 구성
     *   변수 : 기울기, b
     *   함수 : 교점을 구하는 함수, 교점이 생기는지 아닌지 파악하는 함수
     */
    public class Line {
        double slope;
        double intercept;

        Line(double slope, double intercept) {
            this.slope = slope;
            this.intercept = intercept;
        }

        /*
         * 교점을 구하는 함수
         * 반환값 : x를 대입했을 때의 y값
         */
        public double lineCrossDot(double x) {
            return this.slope * x + this.intercept;
        }

        /*
         * 교점이 생기는지 아닌지 파악하는 함수
         * 반환값 : 교점이 생기면 true 안생기면 false
         */
        public boolean isCrossing(double crossingDot, double buildingHeight) {
            if (crossingDot < 0) {
                return false;
            }
            return crossingDot <= buildingHeight;
        }
    }
}

링크

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

1027번: 고층 건물