[프로그래머스] 기지국 설치 (Summer/Winter Coding(~2018))

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

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

2021-08-25

---

class Solution {
    public int solution(int n, int[] stations, int w) {
      int answer = 0;
      int start = 1;
      for (int station : stations) {
//            answer += Math.ceil(((station - w - start) / (double)((w*2) + 1)));
            int val = station - w - start;
            if(val > 0) {
                int res = val / (2 * w + 1);
                answer += (val % (2 * w + 1)) == 0 ? res : res + 1;
            }
            start = station + w + 1;
        }
        if(start <= n){
            int val = n - start + 1;
            int res = val / (2*w+1);
            if(n == start) answer++; // 끝
            else answer += (val % (2*w+1)) == 0 ? res : res + 1;
//            else answer += Math.ceil(((n - start + 1) / (double)((w*2) + 1)));
        }
        return answer;
    }
}

#문제풀이

아이디어는 기지국이 이미 설치되어 있어서 전파가 닿는 부분을 기준으로, 설치가 되어 있지 않는 구간에 몇개나 설치할 수 있는지 계산했다. 

 

즉, 기지국을 순서대로 돌면서, 기지국이 전파할 수 있는 왼쪽 부분부터 현재 기준점 (start)까지 몇 개의 기지국이 필요한지를 체크한다.

 

그리고, 기지국이 전파할 수 있는 오른쪽 부분부터 그 다음 기지국을 만날 때 까지 같은 방식으로 체크한다. 

 

단, 이미 세워진 기지국을 다 체크했는데도 전파가 끝까지 안 닿는 경우가 있을 수 있다. 그 부분은 n을 기준으로 따로 계산을 해주면 된다.

 

답은 맞는데 계속 틀렸던 부분은 Math.ceil()을 사용해서 효율성에서 시간초과가 났었다.. 직접 계산해주는 것으로 바꾸니 통과되었다.