[프로그래머스 Level 3] 기지국 설치 [Java]

 

 

---

※. 현재위치(position)을 만들고 현재위치가 기지국 왼쪽 범위(i-w)보다 작으면 설치

 

※. 최소로 설치하기 위해서 현재위치에 전파가 없다면 (현재위치 + w) 에 설치한다. 현재위치에도 전파가 도달

 

※. 현재위치가 설치된 기지국 범위에 포함된다면 현재위치를 기지국 오른쪽 범위 밖으로 변경(i+w+1)

 

※. 기지국을 새로 설치했다면 다음 위치는 기지국의 오른쪽 범위 밖(position + w + 1 + w)

 

---

class Solution {
    public int solution(int n, int[] stations, int w) {
        int position = 1;
        int si = 0;
        int answer = 0;
        while(position <= n) {
            if(si < stations.length && stations[si] - w <= position) {
                position = stations[si] + w + 1;
                si++;
            }
            else {
                answer++;
                position += 2*w+1;
            }
        }
        return answer;
    }
}

 

---

※. stations 배열이 자연수 - 무조건 하나 이상의 기지국이 설치되어 있음

 

※. 범위가 닫지 않는 부분들이 2개 이상 있다.

 

※. 범위에 전파가 닿을 수 있도록 최소한의 기지국을 설치

 

---

class Solution {
    public int solution(int n, int[] stations, int w) {
        int position = 0;
        int answer = 0;
        for(int i : stations) {
            int end = i-w-1;
            if(end < 1)
                end = 0;
            
            int dis = end - position;
            position = i+w;
            if(dis < 1)
                continue;
            
            if(dis % (2*w+1) == 0) {
                answer += dis/(2*w+1);
            }
            else {
                answer += dis/(2*w+1) + 1;
            }
            
            
        }
        if(position < n) {
            int dis = n - position;
            
            if(dis % (2*w+1) == 0) {
                answer += dis/(2*w+1);
            }
            else {
                answer += dis/(2*w+1) + 1;
            }
        }
        return answer;
    }
}