[Java] [Summer/Winter Coding(~2018)] Lv3.기지국 설치

문제를 다 읽고 정리해 보자면,

기지국 영향권이 벗어난 곳에 알.잘.딱.깔.센으로 기지국을 세워보자!이다.

 

그럼 이제 이 알.잘.딱.깔.센을 구현하면 된다

처음에는 요즘에 조합으로 푸는 거에 맛들려서, 그냥 조합을 돌려볼까?라고 생각해 봤지만,

• 기지국의 수가 정해져 있지 않고, 구하는 문제이라는 점
• 그렇다면, 1부터 아파트의 수까지 돌려야 하는데 그 아파트의 수 N의 값이 200,000,000 이하의 자연수라는 점

종합하자면, 조합으로는 비효율적이다

(사실, 그냥 N의 크기만 봐도 조합은 아닌 것..)

 

 

그다음으로 맛들린 건, dfs()였는데

구간 내를 탐색하면서 구하면 되겠다고 생각하고 구현했는데, 시초가 나버렸다

 

[실패 코드]

내 코드가 실패인 이유를 몇 가지 정리해 보자면,

1. getStation() 메소드에서 재귀호출이 과하게 반복되고 있다.
2. 기지국이 설치된 후, 해당 기지국의 전파 범위 내의 모든 구역을 일일이 확인하고 있다.

import java.util.*;

class Solution {
    int n;
    int w;
    int count = 0;
    HashMap<Integer, int[]> map;
    boolean [] visited;
    public int solution(int n, int[] stations, int w) {
        this.n = n;
        this.w = w;
        visited = new boolean[n+1];
        map = new HashMap<>();
        
        // 1. 4G -> 5G 바꾸기
        for(int i = 0; i < stations.length; i++){
            int cur_idx = stations[i];
            visited[cur_idx] = true;
            
            // 기지국 전파 전달
            int minIdx = Integer.MAX_VALUE;
            int maxIdx = Integer.MIN_VALUE;
            
            for(int j = 1; j < w; j++){
                if(cur_idx+j <= n){
                    visited[cur_idx+j] = true;
                    maxIdx = Math.max(maxIdx, cur_idx+j);
                }
                if(cur_idx-j > 0){
                    visited[cur_idx-j] = true;
                    minIdx = Math.min(minIdx, cur_idx-j);
                }
            }
            map.put(cur_idx, new int[] {minIdx, maxIdx});
        }
        
        // 2. 추가 기지국
        for(int i = 0; i < stations.length; i++){
            if(i == 0){
                getStation(0, stations[i]);
            }else if (i == stations.length-1) {
                if(stations[i] != n){
                    getStation(stations[i], n);
                }
            }else{
                getStation(stations[i-1], stations[i]);
            }
        } 

        return count;
    }
    
    void getStation(int start, int end){
        int mid = (start+end)/2;    // 기지국 세울 위치
        int cnt = 1;
        int minIdx = Integer.MAX_VALUE;
        int maxIdx = Integer.MIN_VALUE;
        while(cnt <= w){
            if(mid-cnt > 0){
                visited[mid-cnt] = true;
                minIdx = Math.min(minIdx, mid-cnt);
            }
            if(mid+cnt <= n){
                visited[mid-cnt] = true;
                maxIdx = Math.max(maxIdx, mid+cnt);
            }
        }
        
        // 남은 기지국 확인
        for(int i = maxIdx; i < end; i++){
            if(!visited[i]) getStation(maxIdx, end);
        }
        
        count++;
        return;
    }
}

 

 

 

[성공 코드]

피티지랑 다른 사람들의 코드를 보며 열심히 씨름하면서, 얻은 코드이다.

앞에서 본 구역 하나하나를 확인하려고 했던,

나의 실패 코드에 비해 깔끔하다는 걸 한눈에 확인할 수 있다.

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int position = 1;   // 현재 아파트 동 위치
        int idx = 0;        // stations에서의 index
        
        while(position <= n){
            if(idx < stations.length && position >= stations[idx]-w){     // 1. 기지국 설치 X
                position = stations[idx]+w+1;   // 현재 위치의 기지국 영향권+1로 갱신
                idx++;
            }else{
                // 2. 기존의 기지국 영향권 밖 -> 설치 필요
                answer++;
                position += (w*2)+1;
            }
        }
        
        return answer;
    }
}

 

 

그럼 과연 뭐가 다를까?

먼저, 여기서는 아파트의 첫 번째 동, 인덱스 1부터 탐색을 시작한다.

1. stations의 인덱스가 stations보다 작은 지 && 현재 아파트의 위치가, 현재 기지국의 영향권에 드는지 확인한다.

2.1 만약, true 라면 현재로서는 추가적인 기지국 설치가 필요 없다.

    -> 즉, 현재 기지국의 영향권이 끝나는 아파트 +1의 위치로 가면 된다.

  Q.기지국의 영향권이 끝나는 아파트의 위치 어캄?

    A. 하나의 기지국은 +-w 이내에 있는 아파트까지 영향이 가므로

         현재 기지국의 영향권 밖의 아파트 위치는, (현재 기지국 위치 + w) 하면 된다.

2.2 false라면, 추가적인 기지국 설치가 필요하다.

   -> 기지국을 설치하고

  -> (point) 아파트의 위치를 움직인다.

3. 위의 과정을 아파트의 마지막 동까지, 즉 n까지 반복하면 된다.

 

결국, 기지국을 설치하지 않아도, 설치하더라도 아파트의 위치를 옮겨야 하고

아파트의 위치를 옮기는 게 이 문제의 핵심이다!

 

추가 기지국을 설치하지 않을 경우에는, 현재 기지국의 영향권 바로 다음 아파트로 옮기면 돼서

빠르게 생각해 낼 수 있었지만,

기지국을 설치한 후, 아파트는 어떻게 설치해야 하는지 잘 생각이 나지 않았다.

 

Q. 설치하더라도 추가 설치한 기지국의 영향권 밖부터, 그 다음 기지국까지 비어있으면 어캄?

A. 그렇다면, 그림을 그려서 이해를 해보겠습니다~ 

 

n = 14, stations = {10}, w = 2인 경우를 생각해 보겠습니다

그런 postion = 1, idx = 0으로 탐색 시작

 

positon = 1인 처음에는 기지국 영향권 밖이므로, 설치가 필요하다

그렇다면 기지국 설치하고 (answer++)

아파트를 이동하는데, 여기서 포인트!!!

이동한 아파트의 위치는, (현재 아파트의 위치 + (+-) 영향권  + 1)이다.

이 부분이 잘 이해가 안 갔는다.

기지국 설치가 필요하다고 해서, 현재 위치에 그냥 기지국을 설치한다면, 

아파트 1동과 같은 경우에는 양옆으로 영향권이 뻗어가지 못하고, 아래의 그림처럼 +만 영향권을 행세할 수 있다.

 

그렇다면

Q. 어떻게 해야 알.잘.딱.깔.센 기지국 설치 가능?

A. 이 문제에서는 설치된 기지국의 정확한 위치를 요구하지 않으므로, 말 그대로 설치하기만 하면 된다.

따라서, 현재의 위치를 기지국 영향권의 '-' 쪽 끝이라 생각하고 전체 영향권을 구하고,

우리는 다음 아파트로 넘어가면 된다!

위의 과정을 따르면, 그림처럼, 아파트의 위치를 5로 넘어간다.

Q. 6, 7번째는 어캄?

이 경우를 구하기 위해서, 실패코드에서는 매번 visited 배열과 재귀 호출을 이용해서 확인했는데,

여전히 기지국의 인덱스는 10이므로, 똑같이 실행하면 된다.

(stations의 인덱스가 움직일 때는 오로지, 첫 번째 if문을 만족하며 추가 설치가 필요 없을 때이다!)

현재위치 positon = 5에서, 코드로 나타내면

position = 5 + (2*2)+1 = 10,

아파트의 위치는 10으로 움직였다.

else{
   // 2. 기존의 기지국 영향권 밖 -> 설치 필요
   answer++;
   position += (w*2)+1;
}

 

아파트 위치 10에서는 영향권 이내이므로,

현재의 영향권 밖인 아파트, 13으로 이동한다.

이후, 더 이상의 station은 존재하지 않으므로, else문에서 아파트를 추가하고 while은 조건문에 의해 종료된다!

if(idx < stations.length && position >= stations[idx]-w){     // 1. 기지국 설치 X
    position = stations[idx]+w+1;   // 현재 위치의 기지국 영향권+1로 갱신
    idx++;
}

 

이렇게 코드만 보면 어렵지는 않지만

생각하고 이해하는데 시간이 조금 걸렸던 문제였다.