프로그래머스 [Lv. 3] 기지국 설치 {언어 : Java}

문제 링크

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

프로그래머스

정답 코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int range = 2 * w + 1;
        int currentIdx = 1;
        for (int s : stations) {
            // 현재 위치가 기지국의 범위에 있는지
            int left = s - w;
            int right = s + w; 
            if (currentIdx < left) {
                int dist = left - currentIdx;
                answer += (int) Math.ceil((float) dist/range);
            }
            currentIdx = right + 1;
        }
        // 마지막 기지국 이후의 남은 구역 처리
        if (currentIdx <= n) {
            int dist = n - currentIdx + 1;
            answer += (int) Math.ceil((float) dist / range);
        }

        return answer;
    }
}

풀이 방법

1. 현재 범위와 기지국이 도달하는 범위를 비교한다.
2. 유효하지 않은 범위를 기지국을 설치 했을 때 유효해지는 범위 (range = 2 * w + 1)로 나눈 후 올림한다.
   1. 예를 들어 유효하지 않은 범위가 20이고 w가 2라면 range는 5가 되고 기지국은 4개 설치하면 된다.
3. 마지막으로 끝부분에 도달했는지 확인하고 위와 동일하게 계산한다.
4. answer를 반환하면 끝!

느낀점

• 실수를 줄인다면 Lv. 3도 풀 수 있다.

틀린 코드

• dist를 left - currentIdx + 1로 떠올린 것 까지는 좋다.
  • 하지만 left는 이미 유효한 범위이고 dist는 유효하지 않은 범위를 말하므로
  • dist = left - 1 - currentIdx + 1 = left - currentIdx가 된다.
• 또 currentIdx가 n보다 작거나 같아야 된다.
  • 왜냐하면 currentIdx는 기지국에서 닿지 않는 부분을 의미하기 때문이다.

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int range = 2 * w + 1;
        int currentIdx = 1;
        for (int s : stations) {
            // 현재 위치가 기지국의 범위에 있는지
            int left = s - w;
            int right = s + w;
            int dist = left - currentIdx + 1; 
            if (currentIdx < left) {
                answer += (int) Math.ceil((float) dist/range);
                currentIdx = right + 1;
            }
        }
        if (currentIdx < n) {
            int left = n - w;
            int right = n + w;
            int dist = left - currentIdx + 1;
            answer += (int) Math.ceil((float) dist/range);
        }

        return answer;
    }
}