[프로그래머스] 기지국 설치

📌 개요

위치에 따라 번호가 매겨져 있는 아파트들의 옥상에 5G 기지국을 설치하려고 한다. 5G 기지국은 기존에 설치되어 있는 4G 기지국과는 전파의 전달 범위가 다르다. 기존에 4G 가 설치되어 있는 아파트들의 목록을 담은 배열 stations 와 총 아파트의 개수 N, 그리고 5G 기지국을 설치했을 때의 전파 전달 범위를 나타내는 W 가 주어졌을 때, 모든 아파트에 전파를 전달하기 위해 설치해야 하는 기지국의 최소 개수를 구하여라.

 

예) N = 11, stations = [4, 11], W = 1

4번 아파트와 11번 아파트에 전파 전달 범위 1 의 기지국이 설치되어 있으므로, 전파를 전달받을 수 있는 아파트는 위 그림과 같이 3, 4, 5, 그리고 10, 11번 아파트이다.

 

나머지 1, 2, 6, 7, 8, 9 아파트에도 모두 전파가 전달되기 위해 최소 몇 개의 기지국을 더 설치해야 하는지를 묻는 문제이다.

ps. 위 그림의 경우에는 최소 3개는 설치해야 한다. 1, 7, 9 또는 2, 6, 8번 아파트에 설치하면 양쪽 W = 1 만큼의 전파 전달 범위로 전파를 전달해서 모든 아파트가 전파를 전달받을 수 있다. 3개 이하로는 모든 아파트에 전파를 전달할 수 없다.

🦾 첫 걸음

문제를 처음 마주했을 때는 무식하게 풀기 방법이 떠올랐다. 다음과 같은 방법이다:

1. N 개의 모든 아파트의 번호가 1 ~ N 까지 나열되어 있는 자료 구조 (예. 배열이나 리스트) 를 생성한다.
2. stations 와 W 를 참고해서 현재 전파가 전달되는 아파트를 자료 구조에서 제외한다.
3. 자료 구조에 남은 아파트 번호들을 대상으로 증설해야 하는 기지국의 최소 개수를 구하는 연산을 실행한다. 실행되는 연산은 다음과 같다:
   • 예) W 가 1일 때는 아파트 한 대 + 양 쪽의 아파트 두 대 까지 전파가 전달되므로 기지국 하나 당 3대의 아파트가 전파를 전달받는다.
   • 만약 남은 아파트가 10대이면 최소 4개의 기지국을 설치해야 할 것이다. 3대의 아파트에 전파를 전달하는 기지국은 3개를 설치하면 3 * 3 = 9대의 아파트에만 전파를 전달할 것이다. 그러므로 최소 4개가 필요하다.

위의 방식에는 두가지의 문제가 있다:

1. 우선 문제의 조건에서 N 은 2억 이하의 자연수이다. 위 방식의 1번에서는 1부터 N 까지 모두 반복문을 활용해서 자료 구조에 집어넣으므로 최대 2억번을 반복할 것이다. 시간이 많이 소요된다.
2. 전파를 전달해야 하는 아파트의 개수만으로는 정확한 필요 기지국의 최소 개수를 구할 수 없다. 만약 10대가 전파 전달이 필요하다고 가정하면, 10대가 모두 모여 있을 때에만 위 방식의 3번에서 설명하는 연산이 유효하다. 만일 10대의 아파트의 1대마다 이미 기지국이 설치된 아파트들이 껴 있고 이로 인해 각 아파트들이 W 이상 떨어져 있다면 최소 10개의 기지국 설치가 필요하게 된다.

 그래서 처음 고안한 방법은 사용할 수 없었다.

 

💡 두 번째 시도, 긍정적인 결과

조금의 휴식을 취하고 두 번째로 생각해낸 방법은 불린 배열이 false 로 초기화가 된다는 사실을 이용하는 것이었다. 처음 생각한 방식의 1번은 최대 2억 개의 수를 모두 넣어야 해서 시간이 많이 소요된다. 불린 배열은 false 로 초기화되니, 선언만 한 후 2억개 모두의 상태를 변경할 필요 없이 stations 에 있는 기지국 정보를 활용해서 이미 전파가 전달되고 있는 아파트들의 상태만 true 로 바꾸어주면 false / true 로 각 아파트별 전파 전달이 필요 여부를 파악할 수 있는 배열이 만들어질 것이다. 전파가 전달되지 않고 있는 아파트들이 위치한 인덱스의 원소는 초기의 false 로 남고, 반대는 true 로 배열에 저장되기 때문이다. 바로 실행에 옮겼다:

boolean[] onOrOff = new boolean[N]; // false 로 초기화 된다. 모두 전파가 닿지 않는 상황의 초기 상태를 배열로 표현한다.

/* stations 의 정보에 따라 전파가 닿는 아파트들의 정보가 업데이트된다. */

for (int station : stations) {
    for (int j = station - W; j <= station + W; j++) {
        if (j > N || j < 1) continue;
        onOrOff[j - 1] = true;
    }
}

N = 11, stations = [4, 11], W = 1 일 때 onOrOff 배열을 출력하면 아래와 같다:

[false, false, true, true, true, false, false, false, false, true, true]

이로써 onOrOff 배열에는 아파트들의 전파 전달 여부에 대한 정보가 불린 값으로 저장되게 되었다. 출력 결과를 보다 보니까 false 가 연속으로 나오는 구간들이 결국 기지국을 몇 개 설치해야 하는지를 결정짓는다는 결론이 내려졌다. 그 이유는 false, 즉 전파가 전달되지 않고 있는 아파트들이 모여 있는 구간에는 항상 기지국을 최소 1개는 설치해야 할 것이고, 정확히 몇 개 설치해야 하는지는 모여 있는 아파트들의 개수, 즉 여기서는 false 가 연속으로 나오는 구간에 몇 개의 false 가 있는지에 따라 달라지기 때문이다. 쉽게 예를 들어 설명하겠다:

• false 연속 4 개, W = 1 일 때: 기지국은 2개 설치해야 한다. 위에서 잠시 설명했듯이 W 가 1이면 3개의 아파트를 커버할 수 있다. 근데 전파를 전달해야 하는 아파트는 4개이므로 1개로는 모자라고 최소 2개는 설치해야 되게 된다.
• false 연속 2개, W = 1 일 때, 기지국은 1개만 설치하면 된다. W = 1 일 때 최대 3개를 커버할 수 있으므로.

사실 이 예시는 위의 출력 결과를 대상으로 든 예이다. 실제 N = 11, stations = [4, 11], W = 1일 때 설치해야 하는 최소 기지국의 개수는 예시에서 파악한 fasle 연속 구간에 필요한 기지국 설치 개수들의 합인 2 + 1 = 3 개이다.

 

여기까지의 생각을 마친 후, 해야 할 일이 명확해졌다. 바로 false 가 연속으로 나오는 구간들 각각의 false 개수를 파악해서 숫자 배열이나 리스트에 저장하는 일이었다. 위의 출력 결과로부터 배열이나 리스트를 생성하면 다음과 같다:

[2, 4]

false 가 연속으로 2 개 나온 이후 true 가 나오고 다음으로 4 개의 false 가 연속으로 등장하기 때문이다.

 

이러한 리스트 / 배열을 생성하는 코드를 짜보았다:

int count = 0;
int idx = 0;
for (int i = 0; i < onOrOff.length; i++) {
    idx = i;
    while (idx < N && !onOrOff[idx]) {
        count++;
        idx++;
    }
    if (count > 0) {
        numOfFs.add(count);
        count = 0;
        i = idx;
    }
}

중첩된 반복문을 사용해서 !onOrOff[idx], 즉 false 를 발견했을 때, 발견된 위치의 인덱스를 시작으로 이후 원소들이 계속 false 인 한 (false 의 연속 구간, while 문으로 연속 구간을 계속 탐색한다.) count 를 증가시켜서 false 의 연속 구간마다 false 가 몇 개가 있는지를 센다. 아래 if 문은 count 에 변화가 있을 때, 즉 연속 구간이 발견되었을 때 (잊지 말자, false 가 하나만 나오고 멈춰도 연속 구간이다) 연속 구간 내의 false 를 센 count 를 numOfFs 리스트에 저장한다. 그리고 다음 연속 구간이 나왔을 때 false 를 다시 세기 위해 count 를 0으로 초기화시킨다. 그래도 idx 를 i 에 할당함으로서 다음 반복에서는 false의 연속 구간이 끝난 지점의 다음 지점부터 (while 문에서 idx 를 하나 증가시키고 나오기 때문에 다음 지점이다) 탐색을 진행하도록 한다. 결과적으로 중첩된 반복문을 모든 onOrOff 의 원소들에 대해서 돌고 나면, 각 연속된 false 구간 내의 false 의 개수가 구간의 등장 순서대로 차례대로 numOfFs 에 저장되어 있다:

numOfFs = [2, 4]

이렇게 false의 각 연속 구간에서의 개수를 파악하고 나니까 문제의 실마리가 보였다. 여기서 기지국이 최소 몇 개가 필요한지를 구하는 일은 어렵지 않았다. 먼저 W 에 따라 전파를 전달할 수 있는 아파트의 개수를 공식으로 나타내보았다:

1 + (2 * W)

위의 공식을 해석하자면 다음과 같다 - 아파트 자신 (1) 과(+) 양쪽 (2) 에 퍼지는 (*) 전파 범위(W)

 

기지국을 한 대 설치할 때 1 + (2 * W) 만큼의 아파트에 전파가 전달되며 두 가지 상황이 있을 수 있다는 결론에 도달했다:

1. 가능한 범위보다 더 넓은 범위 내의 아파트들에 전파를 전달해야 하는 상황
2. 가능한 범위보다 적은 아파트에 전파를 전달해야 하는 상황

2번 상황은 1대의 기지국으로 모든 문제가 해결되는 상황이다. 1번 상황은 어떨까? 1번 상황은 또 두 갈래로 나뉜다:

• 기지국을 설치해 전파를 전달한 후에 기지국도 모든 가능한 범위를 사용했고 남은 아파트도 없는 상황, 즉 가능한 범위의 배수만큼의 아파트가 있는 상황
• 기지국 n 대를 설치했는데 기지국의 가능 범위를 딱 떨어지게 사용하지 못하고 가능한 범위보다 작은 만큼의 아파트 개수가 남는 상황, 즉 가능한 범위의 배수 + 나머지 의 아파트 개수인 상황

여기까지 논리를 전개하니까 나눗셈 (/) 과 모듈로 (%) 연산을 사용해야 겠다는 생각이 들었다. 아래처럼 표현할 수 있다:

1. A (전파 전달할 아파트 개수, false 연속 구간에서 false의 개수) > (1 + (2 * W))
   
   1. A % (1 + (2 * W)) == 0
   2. A % (1 + 2 * W) > 0
2. A < (1 + (2 * W))

그리고 이 세 가지 상황 각각에서 필요한 기지국의 개수는 아래와 같다:

1. 
   
   1. A / (1 + (2 * W)) - 나누어 떨어진다는 의미는 정확하게 아파트 개수를 가능 범위로 나누었을 때의 몫 만큼의 기지국이 필요하다는 이야기이다.
   2. (A / (1 + (2 * W))) + 1 - 나머지가 있으므로 가능 범위로 커버할 수 있는 아파트 개수만큼이 남는다는 것이다. 그래서 기지국 1개를 추가적으로 설치해야 한다.
2. 1 - 단 1개의 기지국으로 커버할 수 있다. A 에는 양의 정수만 해당된다고 가정한다. 실제로 연속 구간을 파악할 때는 false 가 1개 이상일 때만 세기를 시작했다.

이를 바탕으로 코드를 짰다. numOfFs 에 저장된 각 false 연속 구간에서의 false 의 개수 각각을 대상으로 위의 기지국 파악 공식을 적용한 후 모두 더해서 총 필요한 최소 기지국의 개수를 구한다:

int countMin = 0;

for (int countF : numOfFs) {
    if (countF % ((W * 2) + 1) == 0) {
        countMin += countF / ((W * 2) + 1);
        continue;
    }
    countMin += (countF / ((W * 2) + 1)) + 1;
}

왜 2번 상황이 안 보이냐면 어차피 countF < ((W * 2) + 1)) 인 상황에서도 countF 를 가능 범위로 나누면 몫이 0이 나오고 1을 더하면 1이 되기 때문에 countMin += (countF / ((W * 2) + 1)) + 1; 에서 기지국 1개가 필요하다는 사실을 파악해 더하게 되어서 따로 명시할 필요가 없었다. 결국 몫이 0인 상황을 이용하면 1-1과 1-2 상황만 코드로 짜도 된다.

 

이렇게 해서 코드가 완성되었다. 두 번째 시도에서 나의 코드는 아래와 같았다:

public int completeSpread(int N, int[] stations, int W) {
    boolean[] onOrOff = new boolean[N]; // false 로 초기화 된다. 모두 전파가 닿지 않는 상황의 초기 상태를 배열로 표현한다.

    /* stations 의 정보에 따라 전파가 닿는 아파트들의 정보가 업데이트된다. */

    for (int station : stations) {
        for (int j = station - W; j <= station + W; j++) {
            if (j > N || j < 1) continue;
            onOrOff[j - 1] = true;
        }
    }

    List<Integer> numOfFs = new ArrayList<>(); // 연속 구간에 놓여 있는 false 의 개수들을 쉼표로 분리해서 저장한다.

    int count = 0;
    int idx = 0;
    for (int i = 0; i < onOrOff.length; i++) {
        idx = i;
        while (idx < N && !onOrOff[idx]) {
            count++;
            idx++;
        }
        if (count > 0) {
            numOfFs.add(count);
            count = 0;
            i = idx;
        }
    }

    int countMin = 0;

    for (int countF : numOfFs) {
        if (countF % ((W * 2) + 1) == 0) {
            countMin += countF / ((W * 2) + 1);
            continue;
        }
        countMin += (countF / ((W * 2) + 1)) + 1;
    }

    return countMin;
}

정확도는 100프로, 효율성은 빵점이었다:

 

🚀 마지막 시도, 이렇게 간결하게 짤 수 있다고?

정확성이 100점이었으므로, 더 이상 논리는 건드리지 않기로 했다. 사실 효율성 테스트를 통과하지 못하는 이유는 불보듯 뻔했다. 바로 이중 반복문들을 두 군데에서나 사용하고 있었기 때문이다. 어떻게 해야 이중 반복문을 사용하지 않을 수 있을지 고민하다가 false 초기화를 이용해서 길이 N 의 배열에 아파트의 전파 전달 여부를 담는 방식이 사실 아래에 false 가 연속으로 나오는 구간을 파악하기 위한 준비 단계에 불과하다는 사실을 발견했다. 상태를 나타내는 불린 배열을 만들지 않고도 전파가 전달되지 않는 아파트들의 연속 구간과 구간 내 아파트들의 개수를 구할 수 있을까? 를 생각해보았다.

 

결론부터 말하자면, 가능했다. false 연속 구간은 true 의 위치와 깊은 관련이 있었다. 현재 전파 전달이 되고 있는 아파트들의 위치를 알면, 전파 전달이 안되는 위치도 알 수 있었다. 구간을 모르지 않냐고? 아니다. 전파 전달이 되고 있는 아파트들의 연속 구간을 알면 자연스럽게 그 반대인 전파 전달이 안되고 있는 아파트들의 연속 구간을 알 수 있다. 두 구간들의 연관성을 코드로 정립하기 위해 고민을 하기 시작했다.

 

stations 는 오름차순 정렬이 되어 있다. 즉, stations 의 첫 번째 원소는 항상 기지국이 설치된 아파트들 중 가장 작은 번호를 가진 아파트, 즉 맨 위 개요에서의 그림으로 따지면 맨 왼쪽의 아파트를 가리킨다. 이를 이용하면 첫 전파 전달이 안되는 구간이 1 부터  <stations 의 첫 번째 원소> - <왼쪽으로의 전파 전달 가능 범위> (왼쪽 오른쪽 동일하게 W이다.) 임을 추론할 수 있다. 물론 <stations 의 첫 번째 원소> - <왼쪽으로의 전파 전달 가능 범위> 가 2 이상일 때의 이야기이다. 만약 1 이하이면 아파트 1번으로 시작하는 전파 전달이 되지 않는 연속 구간은 존재하지 않는다. 우리가 알아야 할 것은 연속 구간 내에 몇 개의 아파트가 있는지이다. 1부터 시작하는 연속 구간 내의 아파트 개수를 코드로 나타내면 다음과 같다:

(stations[0] - W) - 1 - 1

1을 한번 더 빼주는 이유는 stations[0] - W 는 전파가 전달되는 아파트이므로 포함하지 않기 때문이다.

좀 더 일반화하자면, 위에서 우리가 알고 싶은 것은 true 가 끝나는 시점부터 다음 true 가 나오는 시점 사이에 false 가 몇 개나 존재하느냐 였다. 위의 공식은 맨 앞부터 개수를 세는 것은 true 가 끝나는 시점이랑 상관이 없기 때문에 1과 stations[0] - W 사이에 몇 개의 아파트가 있는지를 계산했지만, 이후에는 (맨 뒤를 제외하고) 모두 이전 true 가 끝난 시점 과 stations[0] - W 사이에 몇 개의 아파트가 있는지를 계산할 것이다. 맨 뒤에서는 또 다른 상황이 펼쳐지는데, 이는 좀 있다 설명하겠다.

그래서 계속 true 가 끝나는 시점을 추적할 필요가 있다. 변수를 하나 선언해주고, 이름을 ptrToTrueOccurrence 라고 지었다. 대충 true 가 최근 마지막으로 나타났던 위치를 가리키는 포인터 변수라는 의미이다.

 

좀 더 생각해보면, ptrToTrueOccurence 는 가장 처음에는 0이겠지만 (가장 처음에는 아파트 0번째에 true 가 나타났다고 가정해도 된다. 그러면 1부터 전파가 전달되지 않은 아파트의 개수를 세게 된다) 이후에는 진짜 이전 true의 위치, 즉 매 반복 시에 stations 에 있는 원소에 W 를 더한 값이 된다. 그 이유는 기지국이 설치된 아파트에서 W 만큼 전파 전달을 양쪽으로 하기 때문에 인덱스로 따지면 아파트 번호 stations[index] - W 부터 stations[index] + W 까지 전파 전달이 닿고 멈추기 때문이다. 즉, ptrToTrueOccurrence 에는 매번 stations[index] + W 를 할당해주면 다음 반복 시에 이전에 어디서 true 가 멈추었는지 알 수 있고, 정확하게 false 의 연속 구간을 파악할 수 있게 된다. 

 

아까 이후에 설명하겠다고 한 맨 뒤에서의 상황을 보자. 아파트 목록의 맨 뒤는 N 이다. 아파트 N은 다른 아파트의 stations[idx] - W 가 될 수 없다. 그래서 stations 내의 모든 기지국이 설치된 아파트를 이용해 연속 구간 파악을 완료했으면  모두 stations 의 마지막 원소를 기준으로 이전 아파트들의 연속 구간의 파악이 완료된 것이므로 마지막으로 마지막 구간을 파악해야 한다. N 과 ptrToTrueOccurence 사이에 몇 개의 아파트가 있는지 추가적으로 파악하면 된다.

 

이렇게 글로 주저리주저리 쓴 내용을 코드로 작성하면 아래와 같다:

 

List<Integer> numOfFs = new ArrayList<>();

int ptrToTrueOccurrence = 0;

for (int i = 0; i < stations.length; i++) {
    if (i == stations.length - 1 && N > stations[i] + W) {
        numOfFs.add(N - (stations[i] + W));
    }
    int countFalse = (stations[i] - W - 1) - ptrToTrueOccurrence;
    if (countFalse <= 0) {
        ptrToTrueOccurrence = stations[i] + W;
        continue;
    }
    numOfFs.add(countFalse);
    ptrToTrueOccurrence = stations[i] + W;
}

stations 에 있는 모든 기지국이 설치된 아파트의 번호들에 대해, 맨 끝에 도달했고 맨 끝이 현재 기지국이 설치된 다른 아파트에서 커버할 수 있는 범위 안에 들지 않았을 때에는 전파 전달이 필요한 연속 구간을 파악해야 하는 상황이므로 N - (stations[i] + W), 즉 N을 포함한 (N은 전파 전달이 안 되었으므로) stations가 커버하는 최대의 아파트 번호와 N 사이의 아파트 개수 를 계산해서 numOfFs 에 저장한다.

맨 끝에 도달하기 전에는 이전 true 가 마지막 등장한 위치와 현재 탐색 중인 기지국이 설치된 아파트의 전파 전달 범위에서 가장 왼쪽, 가장 작은 번호를 가진 아파트 의 위치 사이에 몇 개의 아파트가 있는지를 countFalse 에 저장한다.

 

그리고 만약 countFalse 가 양의 정수가 아니라면, 즉 아파트가 0개 또는 그 이하 (이하인 경우는 기지국이 연속으로 설치되어 있는 상황에서 발생한다.) 라면 현재 탐색하는 기지국이 설치된 아파트의 최대 전파 전달 가능 위치를 ptrToTrueOccurence 에 저장하고 (true 의 마지막 위치가 될 것이므로) 이후의 동작은 생략한다.

 

양의 정수라면, countFalse 가 파악이 되었으므로 (연속된 구간에서의 전파 전달이 필요한 아파트의 개수) 이를 numOfFs 에 저장하고서 true 가 도달한 위치를 ptrToTrueOccurence 에 저장한다.

 

결국 위 코드는 numOfFs 에 모든 전파가 전달되지 않은 아파트들의 연속 구간에서의 아파트들의 개수를 저장할 것이다.

두 번째 시도에서 false 와 true 로 구성된 배열을 중첩 반복문으로 만들고 또 이중 반복문으로 이 배열에 있는 false 의 연속 구간에서의 false의 개수를 세는 과정을 for 문 하나로 대체했다. 결과적으로 완성된 코드는 아래와 같다:

public int solution(int N, int[] stations, int W) {
    List<Integer> numOfFs = new ArrayList<>();

    int ptrToTrueOccurrence = 0;

    for (int i = 0; i < stations.length; i++) {
        if (i == stations.length - 1 && N > stations[i] + W) {
            numOfFs.add(N - (stations[i] + W));
        }
        int countFalse = (stations[i] - W - 1) - ptrToTrueOccurrence;
        if (countFalse <= 0) {
            ptrToTrueOccurrence = stations[i] + W;
            continue;
        }
        numOfFs.add(countFalse);
        ptrToTrueOccurrence = stations[i] + W;
    }

    int countMin = 0;

    for (int countF : numOfFs) {
        if (countF % ((W * 2) + 1) == 0) {
            countMin += countF / ((W * 2) + 1);
            continue;
        }
        countMin += (countF / ((W * 2) + 1)) + 1;
    }

    return countMin;
}

 

2중 반복문 두 개를 없애니까 훨씬 코드의 길이가 짧아졌다. 또한 결과적으로 효율성 테스트를 모두 통과했다. 

Note
IDE 로 작성할 때 메인 함수에서 실행을 용이하게 하기 위해 메서드를 스태틱으로 작성해놓고 복붙을 하니까 한 개의 효율성 테스트가 실패했다. 혹시나 스태틱으로 메서드의 접근 제어자를 설정한 것이 문제였나 싶어서 지웠는데 효율성 테스트를 모두 통과하는 것을 볼 수 있었다. 스태틱 사용을 주의하자. 😂

🚩 결론

레벨 3이라고 어렵다고 생각하기 보다는 차분하게 어떤 방법을 사용할 수 있을지 고민하고, 한 번에 풀려고 하기보다는 점진적으로 풀이를 발전시키는 방법으로 문제를 풀어도 된다는 사실을 배웠다.

 

🧶 출처

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

프로그래머스