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

https://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번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설치할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

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

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

제한사항

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

---

입출력 예

N	stations	W	answer
11	[4, 11]	1	3
16	[9]	2	3

입출력 예 설명

입출력 예 #2

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

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

[풀이]

이번 문제는 N의 수와 효율성 테스트가 껴있어서 배열을 선언하지않고 선형시간에 마무리 해야되는 문제다.

 

기지국의 인덱스를 활용하여 왼쪽부터 순차적으로 나오는 기지국 하나당 왼쪽 범위(신호가 안닿는 범위)를 구하고 그 범위안에 얼마나 최소의 기지국이 포함되는지 구하는 것이 첫 번째 순서고, 마지막 기지국이 n의 범위까지 커버했는지 안했는지를 파악하여 커버를 하지 못했다면 그 부분의 대한 풀이를 해주는 식으로 문제를 풀었다.

 

n = 13, w = 2

위와 같은 아파트 배열에서 파란색 부분은 기지국이 커버할 수 있는 범위, baseL과 baseR로 범위를 구하고

 

기지국의 왼쪽 부분, right와 left인데 이 둘은 기지국의 영향을 받는다. 즉 right값은 현재 baseL -1 이고, left는 이전 baseR과 같다.

 

n = 13, w = 1

이해를 돕자면 이런 느낌이다.

 

위와 같은 배열에서는 첫 번째 기지국의 왼쪽 범위, 즉 신호가 닿지 않는 곳은 없으므로 다음 기지국으로 넘어간다.

 

다음 기지국에서는 4,5번에 신호가 닿지 않는 부분이 있다. 이제 하나의 식이 필요하다.

 

(right - left) / (w * 2) +1  이 식은 4,5의 범위 즉 2의 범위에서 기지국이 커버할 수 있는 범위 (w*2) +1를 나눈 값이다.

 

대충 0.6이 나올 것이다. 2/3이니까 나머지가 존재하면 정수부분에서 +1을 해준 뒤 result에 합해준다. 존재하지 않는다면 그대로 정수부분을 result에 합해준다. 

 

위와 같은 경우라면 1이 result에 합해졌을 것이다.

 

이런 방식으로 처음부터 끝까지 계산해줄 수 있다. 하지만 조건이 남아있다.

 

기지국이 서로의 범위를 침범 노란색은 이전, 초록색은 현재이다.

left와 right를 보면 left는 이전 BaseR의 영향을 받아 6이 되었고, right는 현재 BaseL의 영향을 받아 5가 되었다.

 

즉, left > right 인 상황은 볼 필요가 없기 때문에 continue로 건너뛰어준다.

 

두 기지국 사이가 모두 커버 됐을 때 

위와 같은 상황은 left == right이다. 이 상황도 모두 커버가 되었으니 continue해준다.

 

예제에 있는 그림이다.

위와 같은 상황에서 반복문이 종료되면 12~16인 상황을 고려하지 못하게 된다.

 

baseR != n 인 상황이다. 이런 상황에서는 위에 사용했던 식을 그대로 사용한다.

(n-baseR) / (w*2)+1  이때도 나머지가 있는지 없는지 판단하여 적절히 값을 부여하면 된다.

 

[코드]

public int solution(int n, int[] stations, int w) {
         int left = 0;            //기지국 범위 외 왼쪽 값
         int right = 0;            //기지국 범위 외 오른쪽값
         int baseL = 0;            //기지국 범위 내 왼쪽 값
         int baseR = 0;            //기지국 범위 내 오른쪽 값
         int result = 0;        //답
         
         for(int i = 0; i < stations.length; i++) {
             int base = stations[i];
             left = baseR;                    //왼쪽 값은 기지국 내 오른쪽 값
             
             baseL = base - w;                //기지국 범위
             baseR = base + w;                //기지국 범위
             
             if(baseL < 0) baseL = 0;        //범위 관리
             if(baseR > n) baseR = n;
             
             right = baseL - 1;                //오른쪽 값은 기지국 내 왼쪽 값 -1;
             if(right < 0) continue;
             if(left==right) continue;        //같다면 이미 기지국 사이가 커버가 되있음
             if(left> right) continue;        //이 경우도 마찬 가지로 이미 커버가 되어있음.
             double temp = (double) (right - left) / ((w*2)+1);
             if(temp % 1 == 0) result += (int) temp;        
             else               result += (int) temp +1;        //딱 떨어지지 않는다면 감싸는 범위가 부족한 것.
         }
         
         
         if(baseR != n) {                                    //만약 기지국이 설치가 끝났어도 n까지 범위가 커버되지 못한다면.
             double temp =(double) (n - baseR) / ((w*2)+1);    //n부터 기지국 까지의 범위를 커버할 수 있는 최소의 기지국 수를 구해준다.
             if(temp % 1 == 0) result += (int)temp;        
             else               result += ((int)temp) +1;
         }
         return result;
     }

프로그래머스 테스트 케이스 통과

느낀 점 : 나름 구상도 잘된 것 같고 풀이도 잘 된 것 같지만 처음에는 조금 생각할 시간이 필요했다. 요즘에는 문제를 풀 때 꼭 a4용지를 옆에 두고 생각을 적으면서 문제를 풀고 있는데 정말 효과가 좋은 것 같다. 오늘 딱 프로그래머스 레벨로 100위권 안에 들었는데 아직 많이 부족하다는 생각이 끊이질 않는다. 더 열심히 해야겠다.