문제

풀이

먼저 w 길이를 이용해서 하나의 기지국의 총 전파 길이를 저장한다.

설치된 기지국을 기준으로 현재 위치부터 설치된 기지국까지 기지국의 전파가 닿지 않는 곳이 있다면 (전파가 닿지 않는 길이 / 총 전파 길이)만큼 기지국을 설치한다. 만약에 0으로 나누어 떨어지지 않는 경우에는 하나를 더 설치해 주어야 한다.
설치를 하거나 다음 기지국을 찾았다면 다음 기지국의 마지막 전파가 닿는 위치에 1을 더해서 다음 위치로 간다.

모든 기지국을 지났다면 마지막 장소까지 얼마나 더 설치해야 하는지 위와 동일하게 진행한다.

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int wLength = w*2+1;
        
        int loc = 1;
        
        for (int station : stations) {
            if (station > w + loc) {
                answer += (station - w - loc) / wLength;
                if ((station - w - loc) % wLength != 0) {
                    answer ++;
                }
        
            }
            
            loc = station + w + 1;
        }
        
        if (n >= loc) {
            answer += (n + 1 - loc) / wLength;
                if ((n + 1 - loc) % wLength != 0) {
                    answer ++;
                }
        }   

        return answer;
    }
}

결과

느낀 점

알고리즘이나 자료구조를 활용해야 한다기 보단 로직을 잘 구상하는 게 중요한 문제라고 느껴졌다.
기지국 사이가 가까워서 추가 설치할 필요가 없는 경우를 고려하지 못해서 처음에 조금 어려움을 느꼈던 것 같다.