[프로그래머스] 기지국 설치 [Java(자바)]

본문은 프로그래머스 K-Digital Credit 강좌를 수강하고 작성한 게시물입니다. 

문제

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

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

 

풀이

본 문제는 그리디 알고리즘에 속하는 문제이다. 

'전파 범위(w)만큼 오른쪽으로 이동해서 기지국을 세운다면 세워진 기지국에 의한 전파의 유효범위가 최대가 된다'라는 아이디어가 핵심이었다.

 

이때, 기지국을 세우고자 하는 위치가 이미 전파 범위 안에 있다면 전파 범위 바깥으로 이동 후에 기지국을 세우면 된다.

 

 

포인터(position)를 이용하면 이를 쉽게 구현할 수 있다.

1. 만약 전파 범위 바깥에 있다면 position에 전파의 범위(2*w + 1)를 더한다.
2. 만약 전파 범위 안에 있다면 position은 전파 범위의 오른쪽(stations[i] + w + 1)이 된다.

 

코드

풀이1

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int stationIndex = 0;
        int position = 1;

        while (position <= n) {
            if (stationIndex < stations.length && stations[stationIndex] - w <= position) {
                position = stations[stationIndex] + w + 1;
                stationIndex += 1;
            } else {
                answer += 1;
                position += w*2 + 1;
            }
        }

        return answer;
    }
}

 

풀이2

이 방법은 처음에 풀었던 방법인데, 조금 지저분하다.

풀이1은 기지국을 계속해서 하나씩 배치하는 방법이라면, 풀이2는 전파가 닿지 않는 영역을 구한 뒤 그 영역의 넓이에 따라 필요한 기지국을 계산하는 방식이다. 영역은 다음과 같이 구할 수 있다.

1. 만약 영역의 넓이(section)가 전파의 범위(2*w + 1)보다 좁다면 기지국 1개를 설치한다. 이때, 영역의 넓이가 음수라면 이미 전파가 닿는 범위이므로 기지국을 설치하지 않는다.
2. 만약 영역의 넓이가 전파의 범위보다 넓다면 몫 + 1 (나누어 떨어진다면 0)개의 기지국을 설치한다.

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int pointer = 1;
        int range = w*2 + 1;

        // stations을 순회하며 아직 전파가 도달하지 않는 구간의 영역과 필요한 기지국의 개수를 더해준다.
        for (int station : stations) {
            int leftSide = station - w;
            int rightSide = station + w;
            int section = leftSide - pointer;

            answer += getMount(section, range, pointer);
            pointer = rightSide + 1;
        }

        // 만약 포인터가 n보다 작거나 같다면 마지막 영역에 필요한 기지국의 개수도 더해준다.
        if (pointer <= n) { // 처음에 if (pointer < n)으로 했다가 틀림
            int section = n - pointer + 1;
            answer += getMount(section, range, pointer);
        }

        return answer;
    }

    public int getMount(int section, int range, int pointer) {
        int mount;

        if (section > range) {
            mount = section % range > 0 ? section/range + 1 : section/range;
        } else {
            mount = section > 0 ? 1 : 0;
        }

        return mount;
    }
}