LV3 기지국 설치

---

문제

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

프로그래머스

 

풀이

 

이 문제의 핵심은 레이더가 닿지 않는 범위를 알아낸 다음, 레이더를 적절하게 설치하는 것이다.

 

위 케이스를 보면 레이더가 닿지 않는곳은 1~2 , 6 ~ 9 이다.

 

어떻게 구할 수 있을까?

 

stations 배열에는 [4, 11]이 존재하고, w는 1이다.

 

6 ~ 9 부분을 생각해보자.

6을 생각해보면 4에서 w만큼 더하고, + 1을 더한 값이고, 9는 11에서 w만큼 빼고 - 1을 뺀 값이다.

그러니까 스테이션 두개 사이에서 위의 식으로 레이더가 닿지 않는 범위를 찾을 수 있는 것이다.

 

 

그리고 여기서 어디에 기지국을 설치할지 앞에서부터 확인하면 되는데, 설치했을 때 레이더가 닿는 범위가 그 이전이나 이후의 기지국과 겹치지 않게 설정해줘야 한다.

 

 

여기서는 w가 1로, 앞뒤로 1만큼 차지하기 때문에 7에 설치하면 가장 베스트 위치가 된다. 이 과정을 반복하면 된다.

그러다가 설치해야 하는 기지국의 위치가 9를 넘어서면, 해당 범위는 끝난것이므로 반복에서 탈출하면 된다. 

(아래사진을 참고해보자)

 

 

조금 예외처리를 해야하는건 저렇게 기지국 사이의 공간은 배열을 활용해 알 수 있으나 가장 앞이나 뒤는 배열로 알 수 없다. 따라서 가장 앞과 뒤를 처리하는 로직을 하나씩 추가해주면 풀 수 있다.

 

코드

import java.util.*;

class Solution {
    
    public int answer = 0;
    public void search(int start, int end, int w){

        if(start > end) return;
        int target = start + w;
        answer++;
        search(target+w+1, end, w);
    }

    public int solution(int n, int[] stations, int w) {

        search(1, stations[0]-w-1, w);
        for(int i=1; i<stations.length; i++){
            search(stations[i-1]+w+1, stations[i]-w-1, w);
        }
        search(stations[stations.length-1]+w+1, n, w);
        return answer;
    }
}

 

후기

 

닿지 않는 범위를 사용해야하는건 빨리 캐치했는데, 그 이후에 좀 헤멨다. 처음에는 그 사이에서 이분탐색으로 기지국 위치를 찾는 줄 알았다. 그러나 이럴경우 중간중간 구멍이 날 수 있었고, 그냥 앞에서부터 반복적으로 수행하는게 답이었다. 

n이 최댓값인 2억이고, 기지국이 1개, w가 1이라고 하더라도 기지국 하나가 3칸을 먹기에 시간에 문제가 없었다. (얼추 최대 탐색은 7천만)