1027 고층 건물

문제

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

입력

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

출력

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

=======

문제 분석

각 위치에서 볼 수 있는 빌딩들의 갯수들 중 최댓값을 출력하는 문제이다.

현재 위치에서 빌딩을 보는 경우는 두가지이다.

1. 바라보는 빌딩의 높이보다 낮은 위치에 있는 빌딩

2. 바라보는 빌딩의 높이보다 높은 위치에 있는 빌딩

이 두 조건을 만족하는 빌딩은 현재 위치에서 그 빌딩을 쳐다볼 때  중간에 높은 빌딩이나 겹쳐지는 빌딩이 없어야 한다.

-> 현재 빌딩이 높이가 6 일때, 바라볼려는 빌딩이 x축으로 2만큼 떨어져있고 높이가 2인데 그 중간에 x축으로 1만큼 떨어져있고 높이가 4인 빌딩이 있다고 가정해보면, 중간에 있는 높이가 4인 빌딩으로 인해 높이가 2인 빌딩은 겹쳐져서 보이지 않게 된다. 

x축으로 3만큼 떨어져있고 높이가 10인 빌딩이 있다면 이때는 중간에 방해되는 빌딩이 없어서 관찰이 가능해진다.

위의 조건들을 만족하는지 판단하는 방법은 기울기이다. 어떠한 빌딩을 바라볼 때 중간에 위치한 빌딩과의 기울기보다 더 크다면 관찰이 가능해진다

현재 위치를 [sx,sy] 라 하고 바라보는 빌딩이 [rx,ry] 라면 

기울기는 (ry-sy)/Math.abs(rx-sx) 가 된다. 이전까지 기록 된 가장 큰 기울기보다 작거나 같다면 이것은 중간에 걸리는 빌딩 또는 겹치는 빌딩이 있다는 것이므로 continue를 해주면 된다.

오답 노트

내가 잘못 생각했던 부분은 이전까지의 기록된 가장 큰 기울기보다 작거나 같은 경우 break를 걸었기 때문이었다. 

그 다음 위치 해 있는 아주 높은 빌딩이 있다면 바라 볼 수 있다는 것을 간과한 것이다.

정답 코드

const main = (input) => {
    const INF = 1_000_000_001;
    const n = +input[0];
    const arr = input[1].split(' ').map((v) => +v);
    let answer = 0;
    for (let i = 0; i < n; i++) {
        let cnt = 0;
        let leftIncline = -INF;
        let rightIncline = -INF;
        const [sx, sy] = [i, arr[i]];
        let leftCnt = 0;
        for (let left = i - 1; left >= 0; left--) {
            const [lx, ly] = [left, arr[left]];
            const incline = (ly - sy) / (sx - lx);
            if (incline <= leftIncline) continue;
            cnt++;
            leftIncline = incline;
            leftCnt++;
        }
        for (let right = i + 1; right < n; right++) {
            const [rx, ry] = [right, arr[right]];
            const incline = (ry - sy) / (rx - sx);
            if (incline <= rightIncline) continue;
            cnt++;
            rightIncline = incline;
        }
        answer = Math.max(answer, cnt);
    }
    console.log(answer);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

main(input);