*Gridland Metro

사이트: HackerRank
난이도: 미디움
분류: Search

문제

그리드 상에 존재하는 기차 트랙 정보가 주어졌을 때, 기차트랙을 제외한 영역에 가로등을 설치하려고 한다. 이 때 설치할 수 있는 가로등의 개수를 반환하라.

1. 나의 풀이

해당 문제를 풀다가 타임아웃 해결을 도저히 못하겠다는 생각이 들어서 문제 해결정도만 하고 다른 사람의 코드를 참조하였다. 그런데 나와 비슷하게 해결한 사람의 코드를 보니 파이썬으로 작성되어 있었고, 자바스크립트로는 타임아웃 해결하기가 꽤 쉽지 않을 거 같다는 생각에 일단 패스하기로 했다.

function gridlandMetro(n, m, k, track) {
    // Write your code here
    const map = [];
    let result = n * m;

    track.forEach(([r, c1, c2]) => {
        if (!map[r]) {
            map[r] = [[c1, c2]];

        } else {
            const ranges = map[r];
            const len = ranges.length;

            for (let i = 0; i < len; i++) {
                const [start, end] = ranges[i];

                if (c1 > (end + 1) || c2 < (start - 1)) {
                    map[r].push([c1, c2]);
                } else {
                    ranges[i][0] = Math.min(start, c1);
                    ranges[i][1] = Math.max(end, c2);
                }
            }
        }
    });

    map.forEach(r => {
        r.forEach(([start, end]) => {
            result += start - end - 1;
        });
    });

    return result;
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.