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문을 돌리도록 생각할 수 있다.