[Programmers / JAVA] 기지국 설치

Question

https://school.programmers.co.kr/learn/courses/30/lessons/12979

프로그래머스

 

---

💡 Solution

W만큼 전파된 후, 해당 상태에서 기지국이 설치된 아파트를 중심으로 왼쪽에 전파되지 않은 아파트 구간이 있다면 해당 구간에서의 필요한 기지국의 개수를 구합니다.

 

만약 W가 1이라면, 하나의 기지국이 전파할 수 있는 아파트는 W * 2 + 1, 즉 3개입니다. 이러한 상황에서 왼쪽에 전파되지 않은 아파트의 개수가 1개라면 기지국은 1개가 필요하고, 2개일 경우에도 1개가 필요합니다. 만약 W * 2 + 1인 3으로 나눠지는 수인 3개라면 "전파되지 않은 아파트 수 / 1 * 2 + 1"인 1개가 필요합니다. 즉 전파되지 않은 아파트의 수가 W * 2 + 1의 배수라면 "전파되지 않은 아파트 수 / W * 2 + 1"개가 필요합니다. 

 

만약 전파되지 않은 아파트 수가 W * 2  + 1개로 나누어 떨어지지 않는다면, "전파되지 않은 아파트 수 / W * 2 + 1 "개 + 1개가 필요하게 됩니다.

 

왼쪽 탐색을 모두 마친 이후, 기존에 설치된 기지국 위치 중 가장 오른쪽에 있는 기지국을 중심으로 오른쪽에도 전파되지 않은 아파트가 있는지 확인하고, 만일 있다면 동일하게 필요한 기지국의 수를 구하면 됩니다. 

 

💻 Code

public static class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int leftStart = 1;

        //처음으로 전파된 후, 기지국 왼쪽에 전파되지 않은 아파트를 탐색
        for (int station : stations) {
            if (leftStart < station - w) {
                answer += install(leftStart, station - w - 1, w);
            }
            leftStart = station + w + 1;
        }

        //오른쪽에 전파되지 않은 아파트가 있다면
        if (stations[stations.length - 1] + w < n) {
            answer += install(stations[stations.length - 1] + w + 1, n, w);
        }

        return answer;

    }

    public int install(int start, int end, int w) {
        int noSpreadCount = end - start + 1;
        int installCount = noSpreadCount / (w * 2 + 1);
        if (noSpreadCount % (w * 2 + 1) != 0) {
            installCount++;
        }
        return installCount; 
    }
}