(프로그래머스) 기지국 설치

문제

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

접근

처음에 기지국의 영향을 받는 시작점과 끝점을 담은 Node에 대한 배열을 만들고 이를 오름차순으로 정렬하였다. 그리고 그 배열을 처음부터 탐색해서 기지국의 영향을 받지 않는 공간에 대해 계산하였다. 아래와 같이 말이다.

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        Node[] nodes = new Node[stations.length];
        
        for (int i = 0; i < stations.length; i++) {
            int mid = stations[i];
            int start = mid - w;
            int end = mid + w;
            
            if (start <= 0) {
                start = 1;
            }
            
            if (end > n) {
                end = n;
            }
            
            nodes[i] = new Node(start, end);
        }
        
        w = w * 2 + 1;
        Arrays.sort(nodes);
        
        int distance = nodes[0].start - 1;
        int answer;
        
        if (0 < distance && distance < w) {
            answer = 1;
        } else {
            answer = distance / w;
            if (distance % w > 0) {
                answer++;
            } 
        }
                
        for (int i = 0; i < nodes.length - 1; i++) {
            int start = nodes[i].end;
            int end = nodes[i + 1].start;
            distance = end - start - 1;
            
            if (0 < distance && distance < w) {
                answer += 1;
            } else if (distance >= w) {
                answer += distance / w;
                if (distance % w > 0) {
                    answer++;
                }
            }
        }
        
        distance = n - nodes[nodes.length - 1].end;
        
        if (0 < distance && distance < w) {
            answer++;
        } else {
            answer += distance / w;
        
            if (distance % w > 0) {
                answer++;
            } 
        }
        
        return answer;
    }
}

하지만 시간초과가 났다. stations의 최대 길이가 2억인데, 이 방법으로 구현하게 되면 최악의 경우 총 4억이라는 시간이 들게 된다. 당연히 시간초과다.

stations의 최대 길이가 2억이라면 배열을 한 번만 돌며 답을 구해야 한다는 의미가 된다. 기존의 생각을 뒤집어 보면 stations가 오름차순으로 정렬되었다는 가정 하에 배열을 돌면서 기지국의 영향을 받지 않는 구간을 구할 수 있을 것이다. 따라서 아래와 같이 코드를 수정하였다.

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;     
        int start = 1;
        int end = stations[0] - w - 1;
        int distance = end - start + 1;
        
        // 처음
        if (distance > 0) {
            answer += distance / (2 * w + 1) + 1;
            
            if (distance % (2 * w + 1) == 0) {
                answer--;
            }
        }
                
        for (int i = 0; i < stations.length - 1; i++) {
            start = stations[i] + w + 1;
            end = stations[i + 1] - w - 1;
            distance = end - start + 1;
                        
            if (0 < distance && distance < (2 * w + 1)) {
                answer++;
            } else if (distance >= (2 * w + 1)) {
                answer += distance / (2 * w + 1) + 1;
                
                if (distance % (2 * w + 1) == 0) {
                    answer--;
                }
            }
        }
        
        // 끝
        start = stations[stations.length - 1] + w + 1;
        end = n;
        distance = end - start + 1;
        
        if (distance > 0) {
            answer += distance / (2 * w + 1) + 1;
            
            if (distance % (2 * w + 1) == 0) {
                answer--;
            }
        }
        
        
        return answer;
    }
}

이 생각을 하고 나서도 문제에서 stations는 오름차순이다는 것을 보지 못해 Arrays.sort(stations);를 적용하였고 시간초과가 한 번 더 났었다. 쉬운 문제임에도 불구하고 문제도 제대로 안읽고 너무 멀리 돌아온 것 같다.

정신 차리자는 의미로 정리하게 되었다.