기지국 설치 [자바]

 

🧫 문제 분석

✔️ 출처

기지국 설치 level 3

📖 문제

 

간단하면서도 생각할게 좀 있는 문제였다.

N은 2억이므로 배열을 만들 생각은 하면 안된다. 

 

stations가 최대 10만이므로 stations을 이용해서 푸는 문제이다. 

 

나는 우선 처음 기지국의 전파범위와 처음 아파트 사이의 거리를 구하고 그 거리가 0이하가 아니라면 

그 거리를 새로운 기지국을 설치했을때 전파범위로 나눈 값을 더했다. 

 

그리고 기지국 사이에도 위와같이 연산을 해주고

 

마지막아파트와 마지막 기지국 사이의 거리도 동일하게 계산해주었다.

 

 

 

이번에 하면서 Math.ceil 과 직접 나누기와 나머지연산을 더하는 식으로 2가지로 해봤는데

좋은 경험을 한 것 같다.

 

- 664 / 667 을 연산했을 때 -0.9955 정도의 값이 된다. 

 

Math.ceil(-664/667) 을 하면 Math.ceil은 

음수에서  올림을 하면 

-0.0 과 -1.0 에서는 -0.0이 더 큰 수 이므로 -0.0으로 반환한다. 

 

나머지 연산의 경우를 생각해보자

 

-664 / 667 + -664 % 667 == 0 ? 0 : 1

이때 -664%667 = -664 이므로 1을 반환한다.

 

단순히 내가 <= 0 으로 해도 되었지만 

이걸 몰라서 음수의 올림에 대해서 다시한번 상기하는 계기가 되었다. 

 

 

테스트 케이스를 공유 (본인이 직접 만듦)

10 [9] 1  return 3
10 [1,5,8] 1 return 2
10 [2,5] 333 return 0

---

🔅 문제 풀이 (ceil)

class Solution {
    // n 이 2억이니 배열로는 불가, O(n) 불가능
    // stations만을 가지고 풀어야함
    // stations의 값들의 범위를 구하고 전체 범위에서 뺀다음 그 나머지를 W*2 + 1로 나누자.
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int waveRange = w * 2 + 1;
        
        // 처음 기지국이 전파 도달 거리가 1번아파트까지 닿지 않을 경우
        if (stations[0] - w > 0) {
           answer += Math.ceil((double)(stations[0] - w - 1) / waveRange);
        }
        
        // 기지국 사이의 전파거리가 안닿는 곳도 채움
        for (int i = 1; i < stations.length; i++) {
            int twoApartDist = (stations[i] - w) - (stations[i-1] + w) - 1;
            answer += Math.ceil((double)twoApartDist / waveRange);
        }
        
        
        // 마지막 기지국이 마지막 아파트에 닿지 않을 경우
        if (stations[stations.length - 1] + w < n) {
            answer += Math.ceil((double)(n - (stations[stations.length - 1] + w)) / waveRange);
        }

        return answer;
    }
}

double형으로 바꾸고 ceil 연산을 해야하니 더 느릴수 밖에 없다.

그런데 가독성은 이게 더 좋아보인다. 

 

🔅문제 풀이 (나머지 연산)

class Solution {
    // n 이 2억이니 배열로는 불가
    // stations만을 가지고 풀어야함
    // stations의 값들의 범위를 구하고 전체 범위에서 뺀다음 그 나머지를 W*2 + 1로 나누자.
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int waveRange = w * 2 + 1;
        
        // 처음 기지국이 전파 도달 거리가 1번아파트까지 닿지 않을 경우
        if (stations[0] - w > 0) {
           answer += (((stations[0] - w - 1) / waveRange) 
               + ((stations[0] - w - 1) % waveRange == 0 ? 0 : 1));
        }
        
        // 기지국 사이의 전파거리가 안닿는 곳도 채움
        for (int i = 1; i < stations.length; i++) {
            int twoApartDist = (stations[i] - w) - (stations[i-1] + w) - 1;
            
            answer += ((twoApartDist / waveRange) + (twoApartDist % waveRange <= 0 ? 0 : 1));
        }
        
        
        // 마지막 기지국이 마지막 아파트에 닿지 않을 경우
        if (stations[stations.length - 1] + w < n) {
            int tmp  = n - (stations[stations.length - 1] + w);
            answer += ((tmp / waveRange) + (tmp % waveRange == 0 ? 0 : 1));
        }

        return answer;
    }
}

 

❗ 오답노트 / 필요한 지식

1. 이번 문제의 경우 조건 처리가 부족했었다. 수 계산은 항상 경계를 기억하자.