[백준] 1027번 - 고층 건물 [Java]

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

 

[백준] 1027번 - 고층 건물 [Java]

[백준] 1027번 - 고층 건물 [Java]

---

1.  아이디어

 

현재 빌딩에서 특정 빌딩이 보이는지 여부를 CCW 알고리즘을 통해 구한 외적 벡터의 방향으로 알 수 있다는 점을 이용했다.

---

2. 문제풀이

 

현재 빌딩의 지붕에서 특정 빌딩의 지붕이 보이는지 판단할 때 기준점에 대해 CCW를 통해 방향이 양의 값이면 보이는 빌딩이고 0이면 접하는 빌딩, 음이면 기준점에 가려진 빌딩이라는 점을 이용했다.

 

기준점은 현재 빌딩에 대해 빌딩의 바닥을 기준으로 하고 보이는 빌딩을 찾으면 해당 빌딩의 지붕으로 옮겨준다.

보이는 빌딩에 대해 나중에 해당 빌딩에서 현재 빌딩을 비교할 때도 당연히 보이는 빌딩으로 판단하기 때문에 한번 확인하면 양쪽 모두 보이는 빌딩으로 체크를 해주고, 대신 현재 빌딩에서 오른쪽에 있는 빌딩만 보이는 지 판단하는 방식으로 구현했다.

 

빌딩의 바닥과 지붕을 좌표 평면에 매핑하면 간단하게 이해할 수 있다.

---

3. 코드

 

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

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

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

        int[] heights = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        int[] cntArr = new int[N];

        for (int i = 0; i < N - 1; i++) {
            int xPivot = i;
            int yPivot = 0;

            for (int j = i + 1; j < N; j++) {
                if (!cross(i, heights[i], xPivot, yPivot, j, heights[j])) {
                    cntArr[i]++;
                    cntArr[j]++;
                    xPivot = j;
                    yPivot = heights[j];
                }
            }
        }

        int max = 0;
        for (int cnt : cntArr) {
            max = Math.max(max, cnt);
        }

        System.out.println(max);
    }

    private static boolean cross(int x1, int y1, int x2, int y2, int x3, int y3) {
        return ccw(x1, y1, x2, y2, x3, y3) <= 0;
    }

    // CCW 알고리즘
    private static long ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
        return (x1 * y2 - x2 * y1) + (x2 * y3 - x3 * y2) + (x3 * y1 - x1 * y3);
    }

}

---

4. 후기