프로그래머스 - 기지국 설치 [자바]

• 문제 링크 : 기지국 설치

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

 

정답 X (Solution) (시간초과)

import java.util.*;

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

        List<Integer> iList = new ArrayList<>();

        int now = 1;

        for(int num : stations){
            iList.add(num - w - now);
            now = num + w + 1;
        }

        if(now <= n){
            iList.add(n + 1 - now);
        }


        for(int num : iList){
            answer += num / cover;
            if(num % cover > 0){
                answer++;
            }
        }

        return answer;
    }
}

 

분석

• 효율성이 매우 중요한 문제
• for문을 연달아 2번만 사용해도 효율성 테스트에서 통과하지 못한다.

 

참고할 만한 정답(Solution)

 

1. while을 사용하여 전체의 과정을 한번에 계산(그리디)

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int si = 0;
        int position = 1;
        while(position <= n){
            if(si < stations.length && stations[si] - w <= position){
                position = stations[si] + w + 1;
                si += 1;
            }else{
                answer += 1;
                position += w * 2 + 1;
            }
        }

        return answer;
    }
}

 

2. 첫번째, 중간, 마지막 기지국으로 나눠서 생각하기

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int range = 2 * w + 1;
        int mid = 0;
        //첫 번째 기지국 전의 설치 개수
        answer += cal(stations[0] - w - 1, range);
        //마지막 기지국 후의 설치 개수
        answer += cal(n - stations[stations.length - 1] - w, range);
        //중간 기지국 설치 개수
        for(int i=1; i<stations.length; i++) {
            answer += cal(stations[i] - stations[i - 1] - range, range);
        }

        return answer;
    }
    public int cal(int length, int range) {
        if(length <= 0) return 0;
        if(length % range == 0) return length / range;
        else return length / range + 1;
    }
}

 

비교 분석

• 첫번째 시간초과 정답과는 반복문이 1회 차이가 난다.
• 그리디 알고리즘을 이용해서 한번의 for문 또는 2번의 풀이 처럼 첫번째와 마지막을 분리하여 중간에서만 한번 for문을 돌리도록 생각할 수 있다.