[pro] 프로그래머스 level3 12979 기지국 설치 (Java) - 그리디

[문제]

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

프로그래머스

 

[풀이]

1동부터 n동까지 돌며 그리디하게 기지국을 설치한다.

만약 이미 설치된 기지국 범위 안에 있다면 기지국을 새로 설치할 필요가 없다. 따라서 기지국의 오른쪽 끝 범위 + 1 위치로 이동한다.

만약 설치된 기지국 범위 안에 없다면 새로 기지국을 설치해야 한다. 따라서 설치개수를 증가시켜 주고 새로 설치한 기지국의 전파 범위 다음 위치로 이동시켜줘야 한다. 이때 범위는 (왼쪽으로 w 범위 + 오른쪽으로 w 범위 + 설치되는 곳 1) 이 된다. 

 

[코드]

 

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        //증설해야 할 기지국 개수의 최솟값을 리턴
        
        int idx = 0;
        int pos = 1;
        while(pos<=n){
            //이미 설치된 기지국 범위 안에 있으면
            if(idx<stations.length && stations[idx]-w <= pos){
                //기지국 오른쪽 끝 + 1 위치로 이동
                pos = stations[idx]+w+1;
                idx++;
            }
            else{
                answer++; //기지국 설치
                pos += 2*w+1; 
            }
        }
        return answer;
    }
}