[프로그래머스] 기지국 설치 (Java)

문제

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

코딩테스트 연습 - 기지국 설치

기지국 설치

풀이

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

시간 초과에 유의해서 풀어야 한다. N이 2억개이므로, N으로 순회를 한다면 시간초과가 발생한다.

station정보가 이미 정렬되어 있기 때문에 차례대로 순회하면서 

커버가 되지 않는 영역을 찾아서 coverage수로 나눠주었다. (나머지가 있는 경우 +1)

 

나의 경우는 세 가지 경우로 나누어서 기지국 개수를 구하였다. 

1. 이미 설치된 첫 기지국의 커버리지가 첫 번째 아파트를  포함하지 않는 경우 

: 해당 기지국이 커버하는 첫 번째 영역 기준으로 이전을 분리하여 설치해야 할 기지국 개수를 구한다. 

2. 현재 기지국이 커버하는 첫 번째 영역 - 이전 기지국이 커버하는 마지막 영역 > 0 보다 클 경우

: 두 기지국 사이에 커버하지 않는 영역이 있는 것이므로 해당 영역을 분리하여 설치해야 할 기지국 개수를 구한다. 

3. 마지막 기지국의 마지막 영역이 N이 미만인 경우

: 마지막 부분에 커버되지 않은 부분이 있으므로 N-마지막 기지국의 마지막 영역을 분리하여 기지국 개수를 구한다. 

소스코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int prev = 0, cur = 0;
        int cover = 2*w + 1;
        for(int i = 0 ; i < stations.length; i++) {
            if(i == 0){
                if(stations[i] - w > 1) answer += calc(stations[i] - w -1, cover);
                prev = stations[i] + w;               
                continue;
            }
            cur = stations[i] - w;          
            if(cur - prev > 0) answer += calc(cur - prev -1, cover);           
            prev = stations[i] + w;
        }        
        if(prev < n) answer += calc(n - prev, cover);
        
        return answer;
    }
    
    public int calc(int seg, int cover){       
        return (seg%cover == 0) ? seg/cover : seg/cover + 1;
    }
}