[프로그래머스 ,Java] Level3: 기지국 설치

 

문제분석

 

문제 목표:   모든 아파트에게 전파 송신하기위한 최소 전파탑의 갯수

 

특징 1.  이미 설치된 전파가 있음.

 

 

이 문제를 읽어보고 풀기전에   제한사항을 보면 아파트의 갯수가 2억이다.

 

저 어마어마한 숫자를 보고  아파트 갯수는 for문 돌리면 안대겟구나 라고 느낄것이다..

 

 

따라서, 조금 아이디어가 필요하다.

 

Ex) 만약  이미 설치된 전파가 없으면 어떨까?

 

-> 그렇다면   전체 아파트 갯수 / 전파의범위가 될것이다. (단, 나머지가 존재하면 +1)

 

예로 아파트가 24며  전파가 1이면,  전파범위는 3이될것이고  최소 8개가 필요하다.

 

 

 

 

 

전파탑이 미리 설치된 경우의 전략은 어떻게 하면될가?

 

 

전파탑을 마치   배열을 절단하는도구??로 생각해보자.

 

 

예시로, 아파트가 20개  전파가 1, 미리 전파탑이 10지역에 설치됫다면

아파트 배열은  1~8   과  12~20 으로 텅빈 배열이 나타난다.

 

1~8에서  앞서 생각한  아파트/범위 연산으로 최소 전파탑을 구하면된다.

 

 

 

생각한 로직을  코드로 구현해보자.

 

전파가 안통하는 배열을 추적할  Start 와 End 를 생성하자.

 

Start는  전파가 안통하는 구역의 스타트

end는   전파가 안통하는 구역의 끝부분이다.

 

이를,  (End - Start) / 전파 범위 로직을 통해 최소 전파탑을 구한다.

 

Start와 End는 각각  전파탑이 설치된 지역 - 전파길이 , 전파탑이 설치된 지역 +전파길이가 될수있다.

 

 

-----------------------------------------------------------------------------------------------------------

 

 

여기서 끝나진 않는다.  예외처리를 해줘야한다.

 

 

1. Start가  End보다 클 경우가 나타날수 있다. 

 

 이 경우는 미리 배치된 전파탑이  연속 으로 배치된 경우다.

 

이런경우는  Continue; 제외시켜주자.  안그러면  최소전파탑을 -1 작업을 해서 답이 틀리게된다.

 

 

2.  for문을 전부돈뒤,   마지막 지점 ~  아파트갯수 지점도 놓치면안된다.

근데 이부분은 누구라도 눈치채고 예외처리 햇을것같다.

 

전체문제풀이

 

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
 
        int start=0;
        int end=0;
        
        int scope=w*2+1;
        
        
        for(int i =0;i<stations.length;i++){
            end=stations[i]-w;
            if(end<1){
                end=1;
            }
                   
            if(start<end){
                 int size=(end-start-1)/scope;
                 if((end-start-1)%scope!=0) size++;
                 answer+=size;
            }
            
            start = stations[i]+w;
            if(start>n){
                start=n;
            }
        }
        
        //마지막 end -> 끝 Station
        if(start==n) return answer;
        
        answer+= (n-start)/scope;
        if((n-start)%scope!=0) answer++;
        
        return answer;
    }
}