알고리즘(기지국 설치)

[기지국 설치]

 

* 알고리즘

• 그리디 알고리즘

 

* 로직

• 현재 위치를 1부터 시작하고, 설치된 기지국 위치를 기준으로
  • W 범위 내에 포함되어 있지 않다면 (stations[i] - w > 현재 위치)
    • 현재 위치 += (2*w + 1)을 통해 범위가 포함되는 최적 위치로 이동시킨다
  • W 범위 내에 포함된다면 (stations[i] - w <= 현재 위치)
    • 현재 위치 = stations[i] + w + 1을 통해 설치된 기지국의 오른쪽 범위를 벗어난 아파트 위치로 이동시킨다
    • 주의할 점은, 만약 설치된 기지국이 더이상 존재하지 않지만 아직 N의 범위를 다 탐색하지 않았다면
      • 마지막 기지국을 기점으로 계속 로직을 진행한다

 

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

        int size = stations.length;
        for(int i=0; i<size; ++i){
            boolean mark = false;
            int station = stations[i];
            if(i == size-1 && stations[i] <= n) mark = true;

            while (base <= n){

                //현재 위치가 station 기준 왼쪽 범위에 속하지 않으면 -> station의 왼쪽 끝 부분으로 옮긴 후 answer 카운팅
                if(base < station - w){
                    base += (2*w) + 1;
                    answer++;
                }

                //station의 범위에 속한다면 -> 위치를 station의 오른쪽 범위를 벗어난 구간으로 이동
                else {
                    base = station + w + 1;
                    if(!mark) break;

                    else {
                        station = n + w + 1;
                        continue;
                    }
                }
            }
        }

        return answer;
    }
}