[프로그래머스 / JAVA] 기지국 설치 (정답 코드)

막히거나 틀린 부분이 있더라도, 그냥 그대로 내가 스스로 작성한 부분들을 기록하고 있다.
미래의 복기용으로 나를 위해 적어둔 기록이다.
(이 사람은 어떻게 실패하거나 성공했는지 살펴보는 용도로도 적합할 것 같다.)

---

최근에는 문제 풀이량을 늘리느라, 블로그에 글을 작성하지 못했다.

그런데 이 문제는 기록해 두면 좋을 것 같아서 올린다.

이 문제의 제약 조건 중에서 나를 멈칫하게 했던 건 아래의 N의 범위이다.

 

N : 200,000,000(2억) 이하의 자연수

 

그래서 이걸 보고 처음 들었던 생각은, "이 인덱스를 전부 순회하게 되면 시간초과가 발생하겠구나" 였다.

그래서 순회는 stations의 정보만을 이용해 진행하자고 생각하고 접근했다.

 

처음에는 아래의 코드에 ArrayList<Integer>의 list를 두고, 각 stations를 돌면서 빈 공간이 탐지되면 ArrayList에 그 빈 공간의 길이를 add 한 뒤에, 제일 마지막에 ArrayList를 순회하면서 Math.ceil()연산을 적용시키면서 기지국의 최소 개수를 구해주었다.

 

그렇게 했더니 정확성 테스트는 다 만족 시켰는데, 효율성 테스트 케이스 4개중 2개에서 시간 초과가 발생했다.

그래서 그냥 ArrayList를 없애고, stations를 순회하면서 빈 공간이 탐지되는 즉시 Math.ceil()연산을 적용시켜 answer에 누적시키는 방식으로 최적화했더니 성공했다.

 

사실 시간초과가 난 이유는 정확히 모르겠다.

내 추측은, ArrayList.add()연산을 수행하는 과정에서 배열의 공간이 부족하면 용량을 늘리고 복사하는 과정에서 O(n)의 시간복잡도가 발생하는데, 이 때 stations의 for문까지 합쳐져서 O(n^2)에 근접하게 된 이유이지 않을까 싶다.

 

나머지 코드 설명은 주석에 달아놓았다.

class Solution {
    public int solution(int n, int[] stations, int w) {
        int lastStart = 0, lastEnd = 0; // 직전 기지국 전파 범위의 시작점, 끝점
        int answer = 0; // 기지국 개수의 최솟값 저장
        int wide = 2*w+1; // 기지국 하나당 커버하는 길이
        for(int station : stations) {
            int start = station - w; // 현재 기지국 전파 범위의 시작점
            int end = station + w; // 현재 기지국 전파 범위의 끝점
            
            if (start - lastEnd >= 1) { // 이전 커버 범위와 현재 커버 범위 사이에 빈공간이 있으면
                int len = start - 1 - lastEnd;
                answer += Math.ceil((double)len / wide); // 예: 빈칸 길이가 6인데, 기지국 커버 범위가 5면, 하나로는 부족하고 하나더 설치해야 한다. 이 부분 고민해볼것.
            }
            lastStart = start;
            lastEnd = end; // 다음 순회를 대비해 바꿔주기
        }
        
        if (lastEnd < n){ // 마지막 기지국 오른쪽 공간에 빈 공간이 생긴다면 처리
            answer += Math.ceil((double)(n-lastEnd) / wide);
        }

        return answer;
    }
}

 

---

하루에 한 문제 이상 꾸준히 풀자.

실수는 많이 할수록, 더 많이 배울 수 있다.

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

프로그래머스