[프로그래머스] 기지국 설치 (08.27)

문제

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

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

 

접근법

처음에는 전파를 받지 못하는 구간을 큐에 저장해서 그 큐를 돌면서 기지국을 설치하는 방법으로 풀었으나

시간초과가 났다.

결국에는 다른 코드를 참고할 수 밖에 없었다.

참고한 코드는 stations 배열의 인덱스와 아파트를 도는 인덱스 두개를 사용해서 while문을 돌리는 코드였다.

자세한 설명은 주석에 작성하였다.

 

코드

• 시간초과 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public class Pair{
        int start;
        int end;

        public Pair(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        Queue<Pair> q = new LinkedList<>();

        int max = w*2 + 1;
        if(stations[0]-w-1 >= 1)
            q.offer(new Pair(1, stations[0]-w-1));

        for(int i=0;i<stations.length-1;i++){
            int start = stations[i]+w+1;
            int end = stations[i+1]-w-1;

            if(start <= end)
                q.offer(new Pair(start, end));
        }

        if(stations[stations.length-1] <= n)
            q.offer(new Pair(stations[stations.length-1]+w+1, n));

        while(!q.isEmpty()){
            Pair poll = q.poll();

            int size = poll.end - poll.start+1;

            answer += size/max;
            if(size%max > 0)
                answer++;
        }


        return answer;
    }
}

 

• 정답 코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        //stations 배열을 도는 인덱스
        int stationIdx = 0;
        //아파트를 도는 인덱스
        int apartIdx = 1;

        while(apartIdx <= n){
            //stationIdx가 유효하고, 아파트 인덱스가 현재 기지국 전파범위에 포함된다면
            if(stationIdx < stations.length && apartIdx >= stations[stationIdx] - w){
                //아파트 인덱스를 기지국 전파범위 오른쪽 밖으로 옮기고
                apartIdx = stations[stationIdx]+w+1;
                //다음 기지국으로 이동
                stationIdx++;
            //전파를 받지 못하는 곳이라면
            }else{
                //기지국을 설치하고
                answer++;
                //아파트 인덱스를 기지국이 최소한으로 설치되게끔 최대범위를 더해준다.
                //예를 들어 apartIdx가 1이고 w가 2인 경우
                //3번 인덱스에 기지국을 설치할 경우 1,2,3,4,5 가 전파를 받을 수 있다.
                //따라서 apartIdx에 w*2 + 1을 더해주면 하나의 기지국으로 최대 범위만큼 전파할 수 있다.
                apartIdx += (w*2)+1;
            }
        }


        return answer;
    }
}