문제 링크
문제 요약
- 몇개의 기지국을 더 설치해야 모든 아파트를 커버할 수 있을지 계산한다
풀이 흐름
-
첫 접근 방법:
기지국에 커버 되는지 여부를 나타내는 check[N] 배열을 만들어서 for(1~n) 범위를 돌면서 연속된 false의 갯수를 세고, false 갯수를 커버되는 아파트 수로 나눠서 몇개의 기지국을 설치해야 하는지 계산함.
-> 근데 그냥 테스트케이스는 다 맞았는데 효율성테스트에서 다 틀림 -
두 번째 접근 방법:
for문으로 다 돌아서 그런가보다 하고 루프를 덜 돌 방법을 찾아봄. for(stations) 로 바꿔서 현재 기지국이 커버할 수 있는 가장 왼쪽 아파트 위치와 이전에 커버했던 마지막 아파트의 위치 사이에 다른 아파트가 있다면 기지국이 필요할것이라고 생각함. -
이전에 커버한 마지막 아파트 위치 = last_covered
현재 기지국(s)이 커버할 수 있는 가장 왼쪽 아파트 위치 = s-W;
if(last_covered < s-W) answer+=필요한 기지국 갯수; -
근데 이번엔 그냥 테스트케이스 마저 틀려버림. 왜지? 싶어서 디버깅 해보니 진짜 잔 실수가 많았다. % 연산을 써야하는 부분에 / 연산을 쓰고, s-w-last_covered 를 써야 하는데 n-last_covered를 쓰고.. 알아보기 쉬우라고 변수를 길게 쓰고 일일히 변수로 선언하기 귀찮아서 풀어 썼더니 이런 일이 발생했다.
어쨌든 이런저런 오류 끝에 일반 테스트 케이스, 효율성 테스트 모두 통과 했다.
효율성테스트에서 실패 시
1.Loop를 먼저 의심하기
2.Java에서는 primitive 타입을 사용하는 것이 Objective 타입을 사용하는 것 보다 훨씬 빠름
Queue< Integer > 를 사용하지 않고 array의 index를 사용하는 방법이 좋음
코드
풀이 언어 : Java
<1차>
public int solution(int n, int[] stations, int w) {
int answer = 0;
int[] check = new int[n+1];
for(int station : stations) {
int left = (station - w > 1? station - w : 1);
int right = (station + w < n? station + w : n);
for(int i = left;i <= right; ++i) {
check[i] = 1;
}
}
int coverage = 2 * w + 1;
int not_cover = 0;
for(int i=1;i<=n;++i) {
if(check[i] == 0) {
not_cover++;
}
else if(not_cover > 0) {
answer += not_cover/coverage;
if(not_cover % coverage != 0)
answer++;
not_cover = 0;
}
}
if(not_cover > 0) {
answer += not_cover/coverage;
if(not_cover % coverage != 0)
answer++;
}
return answer;
}<2차>
public int solution(int n, int[] stations, int w) {
int answer = 0;
int coverage = 2 * w + 1;
int last_covered = 0;
for(int station : stations) {
if(last_covered + 1 < station - w ) {
int left = station - w;
answer += (left - last_covered-1)/coverage;
if((left - last_covered-1)%coverage != 0)
answer++;
last_covered = station + w;
}
if(last_covered < station + w)
last_covered = station + w;
}
if(last_covered < n) {
answer += (n - last_covered)/coverage;
if((n - last_covered)%coverage != 0)
answer++;
}
return answer;
}