프로그래머스 / 기지국 설치 / java

처음 시도 방법

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

        boolean[] visited = new boolean[n];
        for(int i:stations){
            for(int j=w;j>0;j--){
                if(i-j-1 >= 0)
                    visited[i-j-1] = true;
            }
            visited[i-1] = true;
            for(int j=0;j<w;j++){
                if(i+j <n)
                    visited[i+j] = true;
            }
        }
        
        int idx = 0;
        while(idx < n){
            if(!visited[idx]){
                for(int i=0; i<w*2+1;i++)
                    if(i+idx<n)
                        visited[i+idx] = true;
                answer++;
                if(idx + w < n)
                    idx += w;
                continue;
            }
            idx++;
        }
        
        return answer;
    }
}

visited를 사용해서 기존에 기지국이 설치된 곳과 그 기지국 범위의 영역을 true로 둔 다음 while 문을 통해 처음 인덱스부터 하나씩 탐색하는 방식으로 정답을 구했다. 정확성 테스트는 모두 통과했지만 효율성 테스트에서 모두 시간초과가 나왔다.
주어진 N의 크기가 2억이므로 시간복잡도에서 당연히 불가능한 방식이다.

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

더 효율적이면서도 간단한 방법;;;;
인덱스를 1씩 증가시켜서 탐색하는 방법이 아닌 2*w +1로 해서 탐색 횟수를 최소 반이상 줄이는 방법