Hackerland Radio Transmitters

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

문제

hackerland의 마을은 직선 위치에 존재한다. 이런 마을들의 지도와 송신기의 범위가 주어졌을 때, 전체 마을을 커버할 수 있는 최소 송신기 설치 개수를 반환하라.

1. 나의 풀이

단순히 인덱스를 늘려가면 타임아웃에 걸릴거라고 생각한 나머지 복잡한 연산들을 계산하다가 코드를 잘 정리하지 못해서 시간이 많이 소요된 것 같다...
결국 다 해결하지 못했는데 다음부터는 좀 더 단순하게 생각할 필요가 있을 것 같다.

function hackerlandRadioTransmitters(x, k) {
    // Write your code here
    if (x.length === 1) {
        return 1;
    }

    const sorted = [...new Set(x)].sort((v1, v2) => v1 - v2);
    const len = sorted.length;
    let range = k + 1,
        count = 0,
        flag = false;


    for (let i = 0; i < sorted.length; i++) {
        const distance = i === 0 ? 1 : sorted[i] - sorted[i - 1];
        const sub = range - distance;

        if (flag) {
            if (sub === 0) {
                range = k + 1;
                flag = false;

            } else if (sub < 0) {
                range = (k - Math.abs(sub));
                flag = false;
            } else {
                range = sub;
            }
            
        } else {
            if (sub === 0) {
                count += 1;
                flag = true;
                range = k;

            } else if (sub < 0) {
                count += 1;
                range = k;

            } else {
                range = sub;
            }
        }
    }
    
    if (!flag && range < (k + 1)) count ++;

    return count;
}

2. 다른사람의 풀이

function hackerlandRadioTransmitters(x, k) {
    // Write your code here
    x = x.sort((v1, v2) => v1 - v2);

    let transmitters = 0;
    let i = 0;
    let n = x.length;

    while(i < n) {
      	// 송신기 개수 증가
        transmitters++;

      	// 현재 인덱스에서 k까지의 거리 계산(앞)
        let loc = x[i] + k;

      	// 구한 loc 만큼 i 증가
        while (i < n && x[i] <= loc) {
            i++;
        }

	    // 현재 인덱스에서 k까지의 거리 계산(뒤)
        // 위 루프에서 중앙까지 가고 1 더 증가 시켰기 때문에 i를 1 감소 시킨다.
        loc = x[--i] + k;

      	// 구한 loc 만큼 i 증가
        while (i < n && x[i] <= loc) {
            i++;
        }
    }

    return transmitters;
}