[JAVA 알고리즘]BAEKJOON 1027번 고층 건물

고층 건물

---

문제 설명

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

입력

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

출력

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

제한사항

• 없음

입출력 예

input	return
15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5	7
1 10	0
4 5 5 5 5	2
5 1 2 7 3 2	4
10 1000000000 999999999 999999998 999999997 999999996 1 2 3 4 5	6

---

문제 분석

(i,0)부터 (i, 높이)의 선분으로 빌딩을 나타낸다.

• 순서를 x값으로 높이를 y값으로 만든 좌표값을 이용해 문제를 해결한다.

두 지붕을 잇는 선분이 A와 B를 제외한 다른 빌딩을 지나거나 접하지 않아야 한다. 

• 기울기가 동일하지 않아야 한다.
• 이전의 빌딩에 가려지지 않으려면 이전의 빌딩 보다 기울기가 커야한다.

주어진 빌딩을 기준으로 왼쪽과 오른쪽 두 방향에 순서대로 조건을 확인하고 해당하는 빌딩을 헤아린다.

가장 많았던 빌딩의 수를 출력한다.

손으로 풀기

1. 입력값을 이용해 x, y좌표를 2차원 배열에 넣어준다.
2. 주어진 빌딩의 수만큼 반복을 한다.
3. 해당 빌딩을 기준으로 왼쪽으로 빌딩을 반복하면서 해당 빌딩과의 기울기를 구한다.
4. 왼쪽으로 빌딩 기울기를 구할 때는 해당 빌딩의 x 값이 무조건 높기 때문에 i값이 앞으로 가도록 x 증가량을 계산해 준다.
5. 첫 번째 빌딩이거나 이전 빌딩의 기울기 보다 크면 개수를 헤아리고 이전 기울기를 해당 기울기로 교체해 준다.
6. 오른쪽도 반복해 보이는 빌딩의 개수가 가장 많은 빌딩을 출력한다.

나의 문제풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine());

        // 입력값 입력
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[][] coor = new int[N][2];
        for (int i = 0; i < N; i++) {
            coor[i][0] = i;
            coor[i][1] = Integer.parseInt(stringTokenizer.nextToken());
        }

        int answer = 0;
        // 빌딩을 반복하면서 양쪽으로 빌딩을 확인한다.
        for (int i = 0; i < N; i++) {
            double leftSlope = Double.MIN_VALUE;
            double rightSlope = Double.MIN_VALUE;
            int cnt = 0;

            // 왼쪽으로 빌딩과 기울기를 비교하면서 보이는 빌딩을 헤아린다.
            for (int j = i - 1; j >= 0; j--) {
                // 왼쪽으로 갈 때는 x값이 오히려 작아지기 때문에 절대값으로 양수로 만들어서 기울기를 구한다.
                double leftCurrent = (coor[j][1] - coor[i][1]) * 1.0 / (coor[i][0] - coor[j][0]);

                // 첫 번째 빌딩이거나 이전 기울기 보다 클 경우
                if (leftSlope == Double.MIN_VALUE || leftCurrent > leftSlope) {
                    leftSlope = leftCurrent;
                    cnt++;
                }
            }

            // 오른쪽으로 빌딩과 기울기를 비교하면서 보이는 빌딩을 헤아린다.
            for (int j = i + 1; j < N; j++) {
                // 기울기 구하기
                double rightCurrent = (coor[j][1] - coor[i][1]) * 1.0 / (coor[j][0] - coor[i][0]);

                // 첫 번째 빌딩이거나 이전 기울기 보다 클 경우
                if (rightSlope == Double.MIN_VALUE || rightCurrent > rightSlope) {
                    rightSlope = rightCurrent;
                    cnt++;
                }
            }
            answer = Math.max(answer, cnt);
        }

        System.out.println(answer);
    }
}

죄표를 이용하는 문제들을 풀면서 구현하는 방법도 많이 생각하지만 수학적으로 먼가 공부가 더 많이 된 듯한 느낌이다. 아예 알지 못했던 부분들을 문제를 풀기 위해서 찾아보면서 좌표면평상에서 구할 수 있는 수치들과 연관관계를 알 수 있었고, 예전에는 그냥 공식을 그대로 외워서 적용을 했다면 이번에는 공식 자체를 어떻게 그렇게 적용되는지를 증명을 이용해 이해를 하면서 수학적 지식도 늘릴 수 있었다.
처음에는 이해가 하기 어려워 그림도 그려가면서 공식 풀이를 보다 보니 그래도 이해가 되기 시작했다. 진작에 이런 식으로 수학 공부를 했으면 좀 더 수학을 잘했을지도 몰랐겠다.

---

알고리즘 분류

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

문제 출처 - https://www.acmicpc.net/problem/1027

1027번: 고층 건물