기지국 설치

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

문제설명

• 주어진 파라미터: int n, int[] stations, int w
• 반환값: int
• N개의 아파트, 일부 옥상에 4g 기지국 설치 4g → 5g
• 5g 기지국은 범위가 좁아 전달되지 않는 아파트 발생
• 5g 기지국을 최소로 설치하며 모든 아파트에 전달
• 모든 아파트에 전파를 전달하기위해 증설해야할 기지국의 최소 개수 return

풀이방식

1. 풀이1

   1. 1 - n 까지 돌며 stations를 토대로 커버되는 범위 찾기
   2. 범위 내에 있다면 cur++
   3. 범위 내에 없다면 기지국 설치 + list 추가 + 범위 외로 cur 이동(cur + 2*w+1)

   ⇒ 시간초과(1~n 까지 돌며 늘어나는 array의 범위를 찾는것이 문제)

   ⇒ n만큼 반복하지 않는 방법이 필요

2. 풀이2

   1. stations를 활용하기
   2. station 사이의 공간을 채워야함
   3. 이전 station의 끝 +1 ~ 지금 station -1 이 커버되지 않는 공간
   4. 주의 사항
      1. station의 마지막 부분이 커버하는 범위가 n보다 작을 경우 추가로 뒷부분 커버 필요

코드

(풀이방식1)

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        List<Integer> list = new ArrayList<>();
        int answer = 0;
        int range = 2 * w + 1;
        
        for(int i : stations){
            list.add(i);
        }
        
        int cur = 1;
        while(cur <= n){
            if(!search(cur, w, list)){
                answer++;
                list.add(cur + w);
                cur += range;
            }else{
                cur++;
            }
        }

        return answer;
    }
    public boolean search(int cur, int w, List<Integer> list){
        for(Integer i : list){
            if(cur - i <= w && i - cur <= w){
                return true;
            }
        }
        return false;
    }
}

→ 효율성 테스트 실패

→ n까지 돌며 list 내의 모든 원소들의 범위를 살피며 커버되는지 확인하는 부분이 시간초과 야기

→ 1~n까지 순회 불가

(풀이방식2)

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int before = 0;
        int range = 2 * w + 1;
        
        for(int station : stations){
            // 전파 받지 못하는 아파트 범위 
            int start = before + 1; 
            int end = station - w - 1;
            
            if(start <= end){
                int wifi = (end - start + 1) / range;
                int rest = (end - start + 1) % range;
                answer += wifi;
                
                if(rest != 0){
                    answer += 1;
                }
            }
            
            before = station + w;
        }
        
        // 남은 부분 커버 
        if (before < n) {
            int gap = n - before;
            int wifi = gap / range;
            int rest = gap % range;
            answer += wifi; 
            
            if(rest != 0){
                    answer += 1;
            }
        }
        

        return answer;
    }
}

회고

N: 200,000,000 이하의 자연수 라는 조건 때문에 한번 반복하는 것조차 어려운 문제였습니다. 문제 조건 자체가 다른 방법을 유도한 것으로 보이네요!
문제를 읽고 한번 더 읽는 습관을 통해 문제가 주는 힌트를 잘 찾을 수 있도록 노력합시다!

---

참 어렵쥬잉~?