[programmers] 기지국 설치 - Java

기지국 설치

문제 설명

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 더 많은 아파트 옥상에 기지국을 설치하면 모든 아파트에 전파를 전달할 수 있습니다.

제한사항

• N: 200,000,000 이하의 자연수

• stations의 크기: 10,000 이하의 자연수

• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.

• W: 10,000 이하의 자연수

입출력 예

입출력 예 설명

• 초기에, 1~6, 12~16번째 아파트에는 전파가 전달되지 않습니다.

• 3, 6, 14번째 아파트 옥상에 기지국을 설치할 경우 모든 아파트에 전파를 전달할 수 있습니다.

solution.java

import java.util.*;

class Solution {
    public int solution(int N, int[] stations, int W) {
        int coverage = 0; // 가장 멀리 커버된 아파트를 추적
        int index = 0; // stations 배열에 대한 인덱스
        int additionalStations = 0; 

        int range = 2 * W + 1; // 하나의 기지국의 유효 커버리지 범위

        while (coverage < N) {
            // 다음 기지국에서 커버리지를 확장할 수 있는 경우
            if (index < stations.length && stations[index] - W <= coverage + 1) {
                coverage = stations[index] + W;
                index++;
            } else {
                // 새 기지국을 가장 멀리 발견된 위치에 배치
                additionalStations++;
                coverage += range;
            }
        }

        return additionalStations;
    }
}

핵심 키워드

• 단일 기지국의 범위는 2 * W + 1로 계산한다.

• 반복문으로 모든 아파트를 커버한다.
• 현재 기지국이 coverage를 포함하는 경우 coverage를 업데이트한다.
• 그렇지 않은 경우 가장 멀리까지 노출된 위치에 새 기지국을 추가하고 coverage를 확장한다.
• 모든 아파트가 커버될 때까지 계속 반복한다.

결론!