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

🔗 문제 링크: https://www.acmicpc.net/problem/1027

🔍 해결 과정

건물의 지붕위를 (x, y) 형태의 좌표 형태로 나타낼 수가 있고 좌표의 기울기 크기 비교를 통해서 바라볼 수 있는 건물의 개수를 세는 방식으로 문제를 해결하였습니다. 개수를 셀 때 오른쪽 영역과 왼쪽 영역을 따로 나눠서 생각하였습니다. 예시로 다음과 같은 세 가지 건물이 위치한다고 가정하겠습니다.

 

1️⃣ 오른쪽 영역으로의 고찰

(1, 5) 좌표부터 오른쪽으로 살펴본다고 가정한다면 현재 기울기의 최댓값을 누적시킴으로써 볼 수 있는 최대 건물을 셀 수가 있습니다. 과정은 다음과 같습니다.

• (1, 5)는 현재 기준이 되고 있는 점이므로 기울기는 최솟값 -1억으로 초기화한다.
• (2, 3)과 (1, 5)의 기울기(y 값의 증가량 / x 값의 증가량)는 -2이고 이는 초기값 -1억보다 큰 값이므로 현재 최대 기울기 값은 -2가 되며 건물을 볼 수가 있으므로 카운트한다.
• (3, 6)과 (1, 5)의 기울기는 0.5이고 이는 현재 최대 기울기인 -2보다 큰 값이므로 다시 현재 최대 기울기는 0.5가 되며 건물을 볼 수가 있으므로 카운트한다.

이렇게 (1, 5)에서 오른쪽으로 건물을 볼 때의 개수는 2입니다.

 

2️⃣ 왼쪽 영역으로의 고찰

이번에는 (3, 6) 좌표부터 왼쪽으로 살펴본다고 가정해봅시다. 오른쪽과는 달리 왼쪽은 현재 기울기의 최솟값을 누적시킴으로써 볼 수 있는 최대 건물을 셀 수가 있습니다. 과정은 다음과 같습니다.

• (3, 6)은 현재 기준이 되고 있는 점이므로 기울기는 최댓값 1억으로 초기화한다.
• (2, 3)과 (3, 6)의 기울기는 3으로 초기값인 1억보다 작은 값이므로 현재 최소 기울기 값은 3이 되며 건물을 볼 수가 있으므로 카운트 한다.
• (1, 5)와 (3, 6)의 기울기는 0.5이고 이는 현재 최소 기울기인 3보다 작은 값이므로 다시 현재 최소 기울기는 0.5가 되며 건물을 볼 수가 있으므로 카운트한다.

이렇게 (3, 6)에서 왼쪽으로 건물을 볼 때의 개수는 2입니다.

 

결국 주어진 건물의 높이를 바탕으로 각 건물에서 오른쪽과 왼쪽에서의 볼 수 건물 개수를 세어 최대로 볼 수 있는 건물의 개수를 출력하면 됩니다.

 

---

✏️ 코드

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

public class Main {

    private static final String SPACE = " ";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] buildings = Arrays.stream(br.readLine().split(SPACE))
                .mapToInt(Integer::parseInt)
                .toArray();

        int answer = 0;

        for (int i = 0; i < n; ++i) {
            int currentCount = scanBuildings(buildings, n, i);
            if (answer < currentCount) {
                answer = currentCount;
            }
        }

        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }

    private static int scanBuildings(int[] buildings, int n, int index) {
        double curInclination = -1e9;
        int count = 0;

        for (int i = index + 1; i < n; ++i) {
            double inclination = (double) (buildings[index] - buildings[i]) / (index - i);

            if (inclination > curInclination) {
                ++count;
                curInclination = inclination;
            }
        }

        curInclination = 1e9;
        for (int i = index - 1; i >= 0; --i) {
            double inclination = (double) (buildings[index] - buildings[i]) / (index - i);

            if (inclination < curInclination) {
                ++count;
                curInclination = inclination;
            }
        }

        return count;
    }
}