22866 탑 보기 (자바스크립트)

문제

일직선으로 다양한 높이의 건물이 총 N$N$개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

 i$i$번째 건물 기준으로 i−1$i - 1$, i−2$i - 2$, ..., 1$1$번째 건물은 왼쪽에, i+1$i + 1$, i+2$i + 2$, ..., N$N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 L$L$이라고 가정하면 높이가 L$L$보다 큰 곳의 건물만 볼 수 있다.

바라보는 방향으로 높이가 L$L$인 건물 뒤에 높이가 L$L$이하인 건물이 있다면 가려져서 보이지 않는다.

번호	1	2	3	4	5	6	7	8
높이	3	7	1	6	3	5	1	7
보이는 건물 번호	2	x	2, 4, 8	2, 8	2,4,6,8	2,4,8	2,4,6,8	x

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 N$N$이 주어진다.

두번째 줄에는 N$N$개의 건물 높이가 공백으로 구분되어 주어진다.

 

====

문제 풀이 

이진 탐색을 통해서 해결한 문제였다. 

우선 각 높이별 인덱스를 기록하는 객체를 생성 

const n = +input[0];
const arr = input[1].split(' ').map(Number);

const objectHeights = {};

for (let i = 0; i < n; i++) {
    const h = arr[i];
    objectHeights[h] = objectHeights[h] || [];
    objectHeights[h].push(i);
}

구해진 높이들에 대해 내림차순 정렬 

const sortedHeights = Object.keys(objectHeights)
    .map(Number)
    .sort((a, b) => b - a);

 

높이가 높은 순으로 인덱스를 탐색할 것이다.

우선 빈 배열을 선언한다. 높이가 높으면서 인덱스가 낮은 것부터 탐색을 진행.

배열에 담겨진 요소들은 항상 앞으로 탐색 할 요소들보다 높이가 높다.

이 배열에는 x의 위치인 postion, 양방향으로 자기보다 큰 갯수를 기록할 leftCOunt, rightCount, 그리고 가장 가까운 큰 기둥의 postion을 기록할 closePosition이 있다.

class Query {
    position;
    leftCount;
    rightCount;
    closePosition;

    constructor(position) {
        this.position = position;
        this.leftCount = 0;
        this.rightCount = 0;
        this.closePosition = Infinity;
    }
}

지금 탐색을 시도하는 요소의 position이 기록 된 배열에서 어느 위치에 담길지는 이진 탐색을 통해 구할 수 있다.

const binarySearch = (arr, position) => {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid].position >= position) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left;
};

 

배열에 넣어질 인덱스를 통해 그 인덱스의 왼쪽 요소의 leftCount+1 은 지금 요소의 leftCount가 되고 오른쪽 요소의 rightCount+1이 지금 요소의 rightCount가 된다. 여기서 +1 을 하는 이유는 이미 기록 된 요소는 지금의 요소보다 높이가 높은 것이므로 1개를 더 더해준 것이다. 주의할 점은 넣어질 인덱스가 0 이거나 n일 때는 끝자락 이므로 left와 right에는 0이 기록 된다.

또한 가까운 요소는 번호가 작은 값이 아닌 가장 가까운 번호이므로 지금의 position과 넣어질 인덱스의 position들과의 차이 중 작은 값을 넣어주면 된다. 

지금 탐색 중인 요소와 같은 높이를 가지는 엘리먼트들이 있으므로 배열에 바로바로 넣어주는 것이 아니라 임시 배열에 넣은 뒤 현재 높이의 탐색이 끝나면 순차적으로 넣어준다. 

for (const currentHeight of sortedHeights) {
    const positions = objectHeights[currentHeight];
    const temp = [];
    for (const position of positions) {
        if (stack.length === 0) {
            const query = new Query(position);
            temp.push(query);
        } else {
            const query = new Query(position);
            const idx = binarySearch(stack, query.position);
            if (idx === 0) {
                query.rightCount = stack[0].rightCount + 1;
                query.closePosition = stack[0].position;
            } else if (idx === stack.length) {
                query.leftCount = stack[idx - 1].leftCount + 1;
                query.closePosition = stack[idx - 1].position;
            } else {
                query.leftCount = stack[idx - 1].leftCount + 1;
                query.rightCount = stack[idx].rightCount + 1;
                const left = Math.abs(stack[idx - 1].position - query.position);
                const right = Math.abs(stack[idx].position - query.position);
                if (left <= right) {
                    query.closePosition = stack[idx - 1].position;
                } else {
                    query.closePosition = stack[idx].position;
                }
            }
            temp.push(query);
        }
    }

    for (const q of temp) {
        const idx = binarySearch(stack, q.position);
        stack.splice(idx, 0, q);
    }
}

closePostion이 초깃값과 같다면 가까운 요소가 없는 것이므로 answer에 0을 넣어주고 그렇지 않다면 left+right , closePostion을 넣어주면 된다.

const answer = [];
for (const q of stack) {
    if (q.closePosition === Infinity) {
        answer.push(0);
    } else {
        answer.push(`${q.leftCount + q.rightCount} ${q.closePosition + 1}`);
    }
}
console.log(answer.join('\n'));

 

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map(Number);

const objectHeights = {};

for (let i = 0; i < n; i++) {
    const h = arr[i];
    objectHeights[h] = objectHeights[h] || [];
    objectHeights[h].push(i);
}

const sortedHeights = Object.keys(objectHeights)
    .map(Number)
    .sort((a, b) => b - a);

class Query {
    position;
    leftCount;
    rightCount;
    closePosition;

    constructor(position) {
        this.position = position;
        this.leftCount = 0;
        this.rightCount = 0;
        this.closePosition = Infinity;
    }
}

const binarySearch = (arr, position) => {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid].position >= position) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left;
};

const stack = [];
for (const currentHeight of sortedHeights) {
    const positions = objectHeights[currentHeight];
    const temp = [];
    for (const position of positions) {
        if (stack.length === 0) {
            const query = new Query(position);
            temp.push(query);
        } else {
            const query = new Query(position);
            const idx = binarySearch(stack, query.position);
            if (idx === 0) {
                query.rightCount = stack[0].rightCount + 1;
                query.closePosition = stack[0].position;
            } else if (idx === stack.length) {
                query.leftCount = stack[idx - 1].leftCount + 1;
                query.closePosition = stack[idx - 1].position;
            } else {
                query.leftCount = stack[idx - 1].leftCount + 1;
                query.rightCount = stack[idx].rightCount + 1;
                const left = Math.abs(stack[idx - 1].position - query.position);
                const right = Math.abs(stack[idx].position - query.position);
                if (left <= right) {
                    query.closePosition = stack[idx - 1].position;
                } else {
                    query.closePosition = stack[idx].position;
                }
            }
            temp.push(query);
        }
    }

    for (const q of temp) {
        const idx = binarySearch(stack, q.position);
        stack.splice(idx, 0, q);
    }
}

const answer = [];
for (const q of stack) {
    if (q.closePosition === Infinity) {
        answer.push(0);
    } else {
        answer.push(`${q.leftCount + q.rightCount} ${q.closePosition + 1}`);
    }
}
console.log(answer.join('\n'));

 

 

const 답변 = [];
for (stack of stack) {
if (q.closeposition === infinity) {
답변 (0);
} 또 다른 {
답변 (`$ {Q.LeftCount + Q.RightCount} $ {Q.ClosePosition + 1}`);
}
}
console.log (answer.join ( '\ n'));