문제

[프로그래머스] 기지국 설치
https://school.programmers.co.kr/learn/courses/30/lessons/12979#

풀이

조건

• 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성한다.
• 어떤 아파트에는 전파가 도달하지 않는다.
• 아파트의 개수 : N
• 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 : stations
• 전파의 도달 거리 : W

풀이 순서

• 전파가 닿지 않는 아파트들의 범위를 구한다.
• 기지국 하나가 커버할 수 있는 범위로 위의 범위(전파가 닿지 않은 아파트의 범위)를 나눈다.
• 나눈 결과를 올림한 값이 해당 범위에서 추가로 설치해야 하는 기지국의 수이다.
  • 이 때, Math.ceil() 함수를 사용하면 시간초과가 난다.
  • 이를 해결하기 위해 모듈러 연산(%)을 사용한다.

코드

Java

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        // 전파가 퍼지는 범위
        int lim = w * 2 + 1;
        
        int start = 1; // 1번 아파트부터 시작
        // 이미 설치된 위치 기준으로 설치해야 하는 아파트들(전파 안 닿는 아파트) 찾기
        for(int i = 0; i < stations.length; i++) {
            int nowStationPos = stations[i]; //  현재 아파트 위치
            
            int end = nowStationPos - w - 1; // 전파 안닿은 위치 중 끝
            // 1번 아파트가 이미 전파가 닿아 있는 경우
            if(end < 1) {
                start = nowStationPos + w + 1;
                continue;
            }
            
            // 현재 전파 닿지 않은 아파트들의 범위
            int len = end - start + 1;
            
            // 그냥 올림 하면 시간초과 남
            // answer += (int)Math.ceil(len / lim);
            
            // 몫, 나머지 구하는 연산으로 올림하는 것과 같은 결과 찾기
            int a = len / lim;
            answer += a;
            int b = len % lim;
            // 나머지가 있으면 기지국 하나 더 설치해야 됨
            if(b > 0) {
                answer++;
            }
            
            // 다음 범위의 시작 
            start = nowStationPos + w + 1;
        }
        
        // 마지막 구역 범위 처리
        int len = n - start + 1;
        if(len > 0) {
            
            // 아래의 연산은 위 for문 안과 같은 연산
            
            // answer += (int)Math.ceil(len / lim);
            int a = len / lim;
            answer += a;
            int b = len % lim;
            if(b > 0) {
                answer++;
            }
        }
        
        return answer;
    }
}

정리

• Math.ceil() 함수를 사용해 시간초과가 났다.
  • 시간초과가 나면 함수를 사용하지 않고 구현하는 연습을 해야한다.
• 기지국을 설치해야 하는 모든 범위를 고려하는 것이 중요했다.