프로그래머스 Lv.3) 기지국 설치

Summer/Winter Coding(~2018)

기지국 설치

코딩테스트 연습 - 기지국 설치

 

풀이

두번의 수정을 거쳤고, 푸는데 20분? 30분?정도 걸린 것 같다.

우선, 문제의 조건에 N이 2억 이하의 자연수 임을 보고 배열은 안된다는 판단을 내렸다. 된다 하더라도 효율이 안좋을 것이기 때문에 사용을 안하려고 마음먹었다.

 

다음으로 stations 배열은 오름차순으로 정렬되어 있다는 것을 보고, 이전에 설치된 5G망과 현재 설치된 5G망 사이에 커버하지 못한 아파트 세대를 구하면 된다고 생각했다.

 

stations를 도는 반복문을 통해 커버하지 못한 아파트 수를 구해주었고, 반복문 이후에는 마지막으로 탐색한 station과 주어진 N까지 커버하지 못한 아파트 세대를 구했다.

 

결과적으로는 70점? 80점? 정도가 나왔던 것 같다.

문제를 다시 생각해보니 마지막에 주어진 N까지 커버할 때, 마지막 커버지점을 N으로 입력한 것을 발견했다.

그래서, n+w+1로 바꿔주어 바로 통과했다.

 

왜 n+w+1인지는 문제의 조건에 따라 생각해보면 쉽다.

특정 지역에 5G망이 설치되어 있다면 좌우로 주어진 W만큼 커버가 가능하다.

내가 검사하려는 식은 좌측의 5G망과 우측의 5G망 사이의 아파트를 검사하기 때문에, 맨 마지막 n+w+1은 주어진 N을 커버하면 안되기 때문이다. n+w+1 -W는 n+1이 되기 때문에, N에 5G망이 없다는 뜻이 되기 때문에 n+w+1로 설정해주었다.

 

같은 이유로 맨 처음 prev를 -w로 초기화 시켜주었다. (0은 없는 아파트기 때문에)

 

getStations 메소드를 만들어 두 5G망 사이에 몇개의 5G망이 신설되어야 하는지를 구했다.

두 기지국 사이에 커버하지 못한 아파트 갯수를 구하고, 하나라도 있으면 기지국을 신설해 줬다.

이 때, cover라는 변수를 만들어 하나의 기지국 당 만들어 커버 가능한 세대수를 저장했다. 아파트의 총 갯수 / cover 를 통해 새로 신설해야하는 기지국 갯수를 구해주었고, 이 때 남은 아파트가 1세대라도 있으면 하나 더 추가해주었다.

 

로직

1. 주어진 stations 배열을 돌면서 이전 기지국과 사이에, 커버하지 못한 아파트 가구수를 구한다.

2. 아파트 가구 수가 한 세대 이상 있다면, 몇 개의 기지국이 필요한지 구한다.

 2-1. 주어진 w를 통해 하나의 기지국 당 커버할 수 있는 세대 수를 구해, 구해진 아파트 가구 수 / 커버 단위 를 통해,

      건설해야하는 기지국 수를 구한다.

 2-2. 2-1에서 나머지가 있다면, 하나 더 신설해준다.

 

 

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int prev = -w;   // 없는 것
        
        for(int spot : stations) {
            answer += getStations(prev, spot, w);
            prev = spot;
        }
        answer += getStations(prev,n+w+1,w);  // 마지막 아파트까지 체크
        
        return answer;
    }
    
    private int getStations(int prev, int spot, int w) {
        int result =0;
        
        int apartments = (spot-w) - (prev+w) -1; // 아파트 수
        int cover = 2*w+1;  // 기지국이 커버 가능한 세대 수
        if(apartments >0) { 
            result = apartments/cover;
            if(apartments%cover !=0) {  // 남은 아파트 수
                result++;
            }
        }
        return result;
    }
}