[프로그래머스/LV3] 기지국 설치 - 수학(Java)

[Summer/Winter Coding(~2018)] 기지국 설치

🙋‍♂️ 들어가며

이 문제는 1 <= stations.length <= 10000

n <= 2억 이라서 구간, 그리디로 풀면 좋겠다는 생각이 들었다

그리고 문제의 구간범위인 2w+1 을 활용할 수 있을 것 같았다

stations이 1개일 때

stations이 2개 이상일 때

각각 나누어 보면 다음과 같다

testcase-1

n = 16
stations = [9]
w = 2
answer = 3

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

이렇게되면 (7~11) 제외하고 (1,6) 그리고 (12, 16)이 필요하다

길이가 1일때는 구간을 중심으로 왼쪽, 오른쪽 계산처리를 해주면 되겠다

testcase - 2

n = 29
stations = [2, 9, 23]
w = 2
answer = 4

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29

이러면 빈구간 (5,6), (12, 20), (26, 29)가 나오게 된다

위 테스트케이스 2개를 보고 든 생각은 빈구간을 커버하기 위해, 첫 시작점(start)을 1로 설정하고, 현재 구간 시작점 - 기존 시작점 >= 1 일때만 계산을 한다.

첫 시작점인 start를 구간마다 갱신을 하는데 물론 길이가 2이상일때만 적용된다

그리고 길이가 2이상이고 마지막 인덱스일때 끝구간도 계산하면된다

✅ 코드 O(N)

class Solution {
    public int solution(int n, int[] stations, int w) {
        
        
        // int n1 = 29;
        // int[] stations1 = new int[] {2, 9, 23};
        // int w1 = 2;
        // res -> 4
        
        
        int res = my_inspector(n, stations, w);
        return res;
    }
    
    
    static int my_inspector(int n, int[] stations, int w) {
        int cnt = 0;
        
        // 예외처리 (stations 길이가 1일때)
        if (stations.length == 1) {
            int idx = 0;
            int start = 1;
            int end = n;
            int s = stations[idx] - w;
            int e = stations[idx] + w;
            
            // 앞구간 처리 (기지국 설치할 곳이 있다면)
            if (s - start >= 1) {
                System.out.println(s-start);
                cnt += (int) (Math.ceil( (double) (s-start) / ((2*w)+1)) );
            }
            
            // 뒷구간 처리 (기지국 설치할 곳이 있다면)
            if (end - e >= 1) {
                cnt += (int) (Math.ceil( (double) (end-e) / ((2*w)+1) ));
            }
            return cnt;
        }
        
        
        // stations.length >= 2 일때
        
        // 0. 구간을 갱신할 첫 시작점
        int start = 1;
        int N = stations.length;
        for (int i = 0; i < N; i++) {
            int s = stations[i] - w;
            int e = stations[i] + w;
            
            // 1. idx 맨처음
            if (i == 0) {
                // 1-1. 길이가 1이상일때만 계산
                if (s - start >= 1) {
                    cnt += (int) (Math.ceil( (double) (s-start) / ((2*w)+1)) );
                }
                // 1-2. 다음 시작점을 갱신
                start = e+1;
            }
            // 2. idx 맨끝
            else if (i == N-1) {
                // 2-1. 길이가 1이상일떄만 계산 (구간 다 커버 못할때)
                if (s - start >= 1) {
                    cnt += (int) (Math.ceil( (double) (s-start) / ((2*w)+1) ));
                }
                // 2-2. idx가 맨끝이니 끝도 계산 (구간을 커버하지 못할때)
                if (n-(e+1) >= 1) {
                    cnt += (int) (Math.ceil( (double) (n-e) / ((2*w)+1) ));
                }
            }
            
            // 3. idx 맨처음과 맨끝사이
            else {
                // 3-1. 길이가 1이상일떄 (구간 다 커버못할때)
                if (s - start >= 1) {
                    cnt += (int) (Math.ceil( (double) (s-start) / ((2*w)+1) ));
                }
                // 3-2. 다음 시작점 갱신
                start = e + 1;
            }
        }
        
        // 4. 횟수 반환
        return cnt;
    }
}