※. 현재위치(position)을 만들고 현재위치가 기지국 왼쪽 범위(i-w)보다 작으면 설치
※. 최소로 설치하기 위해서 현재위치에 전파가 없다면 (현재위치 + w) 에 설치한다. 현재위치에도 전파가 도달
※. 현재위치가 설치된 기지국 범위에 포함된다면 현재위치를 기지국 오른쪽 범위 밖으로 변경(i+w+1)
※. 기지국을 새로 설치했다면 다음 위치는 기지국의 오른쪽 범위 밖(position + w + 1 + w)
class Solution {
public int solution(int n, int[] stations, int w) {
int position = 1;
int si = 0;
int answer = 0;
while(position <= n) {
if(si < stations.length && stations[si] - w <= position) {
position = stations[si] + w + 1;
si++;
}
else {
answer++;
position += 2*w+1;
}
}
return answer;
}
}
※. stations 배열이 자연수 - 무조건 하나 이상의 기지국이 설치되어 있음
※. 범위가 닫지 않는 부분들이 2개 이상 있다.
※. 범위에 전파가 닿을 수 있도록 최소한의 기지국을 설치
class Solution {
public int solution(int n, int[] stations, int w) {
int position = 0;
int answer = 0;
for(int i : stations) {
int end = i-w-1;
if(end < 1)
end = 0;
int dis = end - position;
position = i+w;
if(dis < 1)
continue;
if(dis % (2*w+1) == 0) {
answer += dis/(2*w+1);
}
else {
answer += dis/(2*w+1) + 1;
}
}
if(position < n) {
int dis = n - position;
if(dis % (2*w+1) == 0) {
answer += dis/(2*w+1);
}
else {
answer += dis/(2*w+1) + 1;
}
}
return answer;
}
}
'프로그래머스' 카테고리의 다른 글
[프로그래머스 Level 2] 게임 맵 최단거리 [자바] (0) | 2022.11.15 |
---|---|
[프로그래머스 Level 2] 가장 큰 수 [자바] (0) | 2022.11.13 |
[프로그래머스 Level 2] k진수에서 소수 개수 구하기 [Java] (0) | 2022.10.08 |
[프로그래머스 Level 2] 전화번호 목록 [Java] (0) | 2022.10.05 |
[프로그래머스 Level 2] 뉴스 클러스터링 [Java] (0) | 2022.10.01 |