코딩테스트 연습 - 기지국 설치 (그리디)

# 주소

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

프로그래머스

# 문제

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 더 많은 아파트 옥상에 기지국을 설치하면 모든 아파트에 전파를 전달할 수 있습니다.

이때, 우리는 5g 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

제한사항

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

---

입출력 예NstationsWanswer

11	[4, 11]	1	3
16	[9]	2	3

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다

입출력 예 #2

• 초기에, 1~6, 12~16번째 아파트에는 전파가 전달되지 않습니다.

• 3, 6, 14번째 아파트 옥상에 기지국을 설치할 경우 모든 아파트에 전파를 전달할 수 있습니다.

# 문제 해설 및 코드 리뷰

 

보기보다 간단한데 효율성 체크 때문에 애먹었던 문제입니다.

N값을 보시면 2억까지나 되기 때문에 배열을 만들어서 하시면 시간초과가 났었습니다.

그래서 최초에 정확성은 다맞았던 테스트 코드를 먼저 리뷰하고 정답코드를 보겠습니다.

 

# 정확성 OK, 효율성 X

class Solution {
    static int answer;
    static boolean[] visit;
    public int solution(int n, int[] stations, int w) {
        answer = 0;
        visit = new boolean[n + 1];
        for (int temp : stations) {
            int start = Math.max(1, temp - w);
            int end = Math.min(n, temp + w);
            for (int j = start; j <= end; j++)
                visit[j] = true;
        }
        int index = 1;
        int a = index;
        int b;
        boolean isOk = false;
        while(index <= n){
            if(visit[index] && isOk){
                b = index - 1;
                calc(a, b, w, n);
                isOk = false;
            }
            else if(!visit[index]){
                if(!isOk){
                    a = index;
                    isOk = true;
                }
            }
            index++;
        }
        if(!visit[n])
            calc(a, n, w, n);
        return answer;
    }
    static void calc(int a, int b, int w, int n){
        int t = (b - a + 1) / (w * 2 + 1);
        double m = (b - a + 1) % (w * 2 + 1);
        if(m > 0)
            answer += t + 1;
        else
            answer += t;
    }
}

N값이 2억까지나 되다 보니, 배열을 만들어서 각각의 인덱스를 탐색하는건 굉장히 메모리낭비가 심해집니다.

최초로 풀 때 당시에 전 boolean타입의 visit배열을 생성하여 stations의 w만큼의 간격만큼 모두 true로 저장하였습니다.

이후 n번의 루프를 돌면서 false인 부분의 시작점과 끝점을 체크하여 몇 개의 안테나가 들어갈 수 있는지 계산했습니다.

여기서 중요한 것은 안테나가 어디어디 위치에 들어간다기보다는 최소한 몇 개가 들어가는지를 따지는게 중요합니다.

예를 들어 5개의 빈공간이 있을 때 w가 1인 안테나를 설치한다고 해봅시다.

그렇다면 1 2 3 4 5라는 인덱스에서 1 3 이렇게 설치해도 될 것이고 2 4 이렇게 설치해도 되고 1 3 5 이렇게 설치해도 될 것입니다.

이것보다 더 많겠지만 중요한 것은 이 안테나가 "어디에" 설치된다기 보다는 "최소한 몇개나" 설치되어야 모두 채워질 수 있냐를 묻는 겁니다.

따라서 빈 공간의 인덱스들을 각각 체크하여 몇갠지 세었습니다.

배열로 생성해서 문제를 풀면 틀리기 때문에 변수타입으로만 풀어보시길 추천드립니다. 그리 어렵지 않습니다. 

정답 코드로 살펴봅시다.

# 정확성 OK, 효율성 OK

class Solution {
    static int answer;
    public int solution(int n, int[] stations, int w) {
        answer = 0;
        int start;
        int end = 1;
        int index = 1;
        for(int i = 0; i < stations.length; i++){
            if(index > n)
                break;
            start = stations[i] - w - 1;
            end = stations[i] + w;
            if(end > n)
                end = n;
            if(start >= index)
                calc(index, start, w);
            index = end + 1;
        }
        if(end < n)
            calc(index, n, w);
        return answer;
    }
    static void calc(int a, int b, int w){
        int t = (b - a + 1) / (w * 2 + 1);
        double m = (b - a + 1) % (w * 2 + 1);
        if(m > 0)
            answer += t + 1;
        else
            answer += t;
    }
}

전 루프무는 굳이 n번 돌지 않고 stations크기만큼만 돌아도 될거같다고 생각했습니다.

따라서 stations의 값을 받아와서 stations에서 w만큼 뺀 값을 start, w만큼 더한 값을 end라 저장했습니다.

이 말이 뭐냐면 start부터 end까지는 모두 전파가 닿기 때문에 (기지국 설치 x) 우리는 1부터 시작하여 start지점까지의 안테나 최소 추가 개수를 구하고 index를 end + 1이라고 저장하면 되는 것입니다.

그러면 다음 탐색 때 index가 이전 지점의 end + 1이니까 다시 거기서부터 start지점까지 안테나 개수를 구할 수 있습니다.

그렇담 안테나 개수는 어떻게 구할 수 있을까요

굉장히 간단합니다.

static void calc(int a, int b, int w){
    int t = (b - a + 1) / (w * 2 + 1);
    double m = (b - a + 1) % (w * 2 + 1);
    if(m > 0)
        answer += t + 1;
    else
        answer += t;
}

예를 들어 봅시다.

인덱스가 1과 4라면 총 1 2 3 4 라는 인덱스므로 4개의 공간이 생깁니다.

w가 1이라 해봅시다.

그렇다면 각 안테나당 차지하는 공간의 크기는? ->> 3이지요.

그렇담 안테나는 대충 암산해서 생각해보면 몇개가 필요하지요??? -> 2개입니다.

즉, 공간의 개수 = (b - a + 1)에서 

전파의 거리 = (w * 2 + 1)만큼의 크기를 나눈 값을 저는 t, 나머지를 m이라 했습니다.

 

왜 나머지를 구하냐면 잘 보세요.

m이 0보다 크다는 것은 하나의 잉여 안테나가 더 필요하단 것을 의미합니다.

아까의 예시에서도 4의 공간 중 전파의 거리 3을 나눴을 때 나머지는 1인데, 1이 잉여 공간으로 남기 때문에 한 개의 안테나 설치를 추가로 해주어야 한단 것을 의미합니다.

따라서 m > 0 이면 나눈 값인 t에 1을 더해주시고 m이 0이면 t만 더해주시면 되는 것입니다.

 

그리고 여기서 끝나면 안되고 end지점을 못찾고 쭉 빈 공간인채로 for문이 끝날 수도 있습니다.

이 때에는 반드시 end가 n보다 작기 때문에 한 번 더 index부터 이번엔 n까지 안테나 개수를 추가로 구하면 되는 것입니다.

그리고 for문 안에 제어문을 3가지 넣어서 정답에 지장받지 않게 해놨는데 첫 번째로

if(index > n)
    break;

 

는 index가 n보다 크면 더 이상 탐색할 필요가 없기 때문에 (범위 초과되어 stations배열이 아직 더 남아있더라도 무시하고 break) 이렇게 설정해주었고

 

if(end > n)
    end = n;

에서 end지점은 Math.min이거로 표현하셔도 무방합니다. n보다 큰 값을 표기하고 싶지 않아서 작성했습니다.

if(start >= index)
    calc(index, start, w);

마지막으로 start가 index보다 더 클 때에만 (안테나 개수 세기 위한 시작지점인 index가 start보다 작을 때 개수를 셀 수 있는데 더 크다면 셀 필요도 없겠죠) 탐색이 가능하므로 이렇게 설정했습니다.

 

풀이가 도움되셨나요?

감사합니다.