기지국 설치

2023.10.16 (FRI)

---

문제 : 프로그래머스 LV.3 - 기지국 설치

---

조건 및 설명

• N개의 아파트가 일렬로 서있음
• 일부 아파트는 원래 4g 기지국이 설치되어 있었음
• w는 전파의 도달거리 (양 옆)
• 설치해야하는 기지국 개수의 최솟값을 구하라.

---

접근법 1

1. 아파트의 갯수만큼 visited[] 배열을 만든다.
2. 이미 기지국의 전파 범위안에 있는 아파트를 true로 바꾼다.
3. 일렬로 세워져있기 때문에, 앞부터 2w+1개씩 세어준다.

임시 결과 코드 1번

/*
 * Title : 기지국 설치
 * Link : https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=java
 */

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        // 1 .
        boolean[] visited = new boolean[n];
        for (boolean v : visited) {
            v = false;
        }
        
        // 2.
        for (int st : stations) {
            int low = st-1-w;
            int high = st-1+w > n-1 ? n-1 : st-1+w;
            
            for (int i = low; i <= high; i++)
                visited[i] = true;
        }
        
        // 3.
        int counter = 0;
        int range = 2*w+1;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && counter < range) {
                counter++;
            }
            
            if (counter == range) {
                for (int j = i; j > i-range; j--)
                    visited[j] = true;
                counter = 0;
                answer++;
            }
            else if ((visited[i] && counter != 0) || (i == n-1 && counter !=0)) {
                for (int j = i-1; j > i-counter-1; j--)
                    visited[j] = true;
                counter = 0;
                answer++;
            }
        }
       
        return answer;
    }
}

채점 결과
정확성: 53.7
효율성: 0.0
합계: 53.7 / 100.0

방법은 맞지만, 정확성 채점에서도 런타임 에러가 발생하였다.
더 효율적이여야 한다.

해당 방법 말고, 새로운 접근법으로 가보자.

---

접근법 2.

1. 기지국 전파가 닿지 않는 구간의 개수를 센다.
2. 그 개수를 range를 이용하여 최소 기지국 설치 개수를 센다.
3. stations이 한개 이상 있기 때문에, 처음-중간-끝을 나눠서 계산한다.

임시 결과 코드 2번

/*
 * Title : 기지국 설치
 * Link : https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=java
 */

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int range = 2*w+1;
        int empty_num;
        
        // 처음
        empty_num = stations[0] - w - 1; // ex) 9 - 2 - 1 = 6
        if (empty_num > 0) {
            answer += empty_num / range;
            if (empty_num % range != 0) 
                answer++;
        }
        
        // 중간
        for (int i = 1; i < stations.length; i++) {
            empty_num = (stations[i] - w) - (stations[i-1] + w) - 1; // ex) 10 - 5 -1
            if (empty_num > 0) {
                answer += empty_num / range;
                if (empty_num % range != 0) 
                    answer++;
            }
        }
        
        // 끝
        empty_num = n - (stations[stations.length - 1] + w);
        if (empty_num > 0) {
            answer += empty_num / range;
            if (empty_num % range != 0) 
                answer++;
        }
            
        return answer;
    }
}

채점 결과
정확성: 70.5
효율성: 29.5
합계: 100.0 / 100.0