[백준] 1027_고층 건물 (Javascript)

문제

BOJ1027_고층 건물

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const buildings = [0].concat(input[1].split(' ').map(Number));
let answer = Array(N + 1).fill(0);

for (let i = 1; i <= N; i++) {
    let rightMax = -Infinity;
    let leftMin = Infinity;
    const x1 = i;
    const y1 = buildings[i];
    // 오른쪽 빌딩 탐색
    for (let j = i; j <= N; j++) {
        if (i === j) continue;
        const x2 = j;
        const y2 = buildings[j];
        const incline = (y2 - y1) / (x2 - x1);
        if (incline > rightMax) {
            answer[i]++;
            rightMax = incline;
        }
    }
    // 왼쪽 빌딩 탐색
    for (let j = i; j >= 1; j--) {
        if (i === j) continue;
        const x2 = j;
        const y2 = buildings[j];
        const incline = (y2 - y1) / (x2 - x1);
        if (incline < leftMin) {
            answer[i]++;
            leftMin = incline;
        }
    }
}
console.log(Math.max(...answer));

풀이

우선 빌딩의 지붕을 잇는 선분의 기울기를 구해야 한다.
직선의 기울기를 구하는 공식은 $\frac{(y_2 - y_1)}{(x_2 - x_1)}$ 이다.

x는 1~N 까지 1씩 증가하고, y는 각 빌딩의 높이로 입력이 주어지기 때문에 이중 반복문을 통해서 한 빌딩을 기준으로 왼쪽에 있는 모든 빌딩까지의 기울기를 구해주고, 오른쪽에 있는 모든 빌딩까지의 기울기를 구해준다.

오른쪽에 있는 빌딩의 기울기를 구할 때는 앞에있는 빌딩보다 기울기가 낮은 빌딩은 보이지 않고, 앞에있는 빌딩보다 기울기가 큰 빌딩만 볼 수 있다. 따라서 기울기의 최댓값을 갱신할 수 있는 빌딩이 등장하면 카운트를 하나 증가시켜주고 최댓값을 갱신해준다.

왼쪽에 있는 빌딩의 기울기를 구할 때는 반대로 앞에 있는 빌딩보다 기울기가 낮은 빌딩은 보이고, 기울기가 큰 빌딩은 볼 수 없다.

이를 이용해서 i번째 빌딩에서 볼 수 있는 빌딩의 개수를 answer 배열에 저장해두고, 배열에 있는 원소 중 최댓값을 구해주면 정답이 출력된다.

코드 (다른 버전)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const buildings = input[1].split(' ').map(Number);
const counts = Array(N).fill(0);

for (let i = 0; i < N; i++) {
    let max = -Infinity;
    const x1 = i;
    const y1 = buildings[i];
    for (let j = i + 1; j < N; j++) {
        const x2 = j;
        const y2 = buildings[j];
        const incline = (y2 - y1) / (x2 - x1);
        if (incline > max) {
            max = incline;
            counts[i]++;
            counts[j]++;
        }
    }
}

console.log(Math.max(...counts));

풀이

위 코드는 왼쪽 빌딩과 오른쪽 빌딩을 따로 분리해서 반복문을 돌지 않는다.
그냥 오른쪽 빌딩들만 확인해주면 되는데 만약 최대 기울기가 갱신되면 i번째 빌딩에서 j번째 빌딩이 보인다는 뜻이고, 반대로 j번째 빌딩에서도 i번째 빌딩이 보인다는 뜻이다. 따라서 count[i]와 count[j]를 둘 다 1씩 증가시킨다.

참고

https://nerogarret.tistory.com/57