프로그래머스: 기지국 설치

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

프로그래머스

설명

처음 이 문제를 풀이할 때, 접근한 방법은 그리디였다.

1. 아파트 배열을 만들고, stations 배열을 순회하면서 stations 배열의 인덱스에서 `-w ~ +w` 까지 방문 표시한다.

2. 아파트 배열을 순회하면서 방문 표시되지 않은 지점을 발견하면,

3. 해당 지점부터 2*w 만큼 이동하고 answer에 +1한다.

=> 하지만 이 경우에 예제는 통과하지만, 히든케이스는 통과하지 못한다. 

=> 또 효율성 부분에서 시간 초과가 발생한다.

 

아파트 배열을 만들지 않고, 한번에 순회하는 방법은 없을까?

방법은 다음과 같다. 

처음 위치부터(now = 1) 전체 길이(n)까지 순회한다. 이때 기지국 범위(stationIdx = 0)를 함께 확인한다.

 

현재 위치가 모든 기지국을 지나친 경우, 현재 위치가 기지국의 범위보다 작은 경우

👉 기지국을 계속 설치해나간다.(answer++)

👉 now를 새로 설치한 기지국 범위 밖으로 이동한다.(now = now + 2 * w + 1)

 

현재 위치가 기지국의 범위보다 작고, 기지국 범위 내에 있는 경우

👉 현재 위치를 해당 기지국 밖으로 이동한다.(w+1)

👉 계산할 기지국을 다음 기지국으로 변경한다.(stationIdx++)

 

평소에 그리디 문제나, 앞부터 쓸고 가야하는 문제들은 기존에 시도한거처럼 전체 배열을 만들고 방문한 지점을 표시한 다음 방문안한 곳은 체크하는 방식을 자주 사용했는데 배열을 만들지 않고 위치를 나타내는 변수만으로 풀이할 수 있는 방법을 고민해봐야겠다.

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        boolean[] apartment = new boolean[n+1];
        
        for(int station : stations) {
            for(int s = station - w; s <= station + w; s++) {
                if(s < 0) continue;
                if(s > n) continue;
                apartment[s] = true;
            }
        }
        
        for(int a = 0; a <= n; a++) {
            if(a >= n) break;
            
            if(apartment[a]) {
                continue;  // 전파가 닿는 곳이면
            }

            a += 2*w;
            answer++;
        }
        
        return answer;
    }
}