[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/12979
[풀이]
1동부터 n동까지 돌며 그리디하게 기지국을 설치한다.
만약 이미 설치된 기지국 범위 안에 있다면 기지국을 새로 설치할 필요가 없다. 따라서 기지국의 오른쪽 끝 범위 + 1 위치로 이동한다.
만약 설치된 기지국 범위 안에 없다면 새로 기지국을 설치해야 한다. 따라서 설치개수를 증가시켜 주고 새로 설치한 기지국의 전파 범위 다음 위치로 이동시켜줘야 한다. 이때 범위는 (왼쪽으로 w 범위 + 오른쪽으로 w 범위 + 설치되는 곳 1) 이 된다.
[코드]
class Solution {
public int solution(int n, int[] stations, int w) {
int answer = 0;
//증설해야 할 기지국 개수의 최솟값을 리턴
int idx = 0;
int pos = 1;
while(pos<=n){
//이미 설치된 기지국 범위 안에 있으면
if(idx<stations.length && stations[idx]-w <= pos){
//기지국 오른쪽 끝 + 1 위치로 이동
pos = stations[idx]+w+1;
idx++;
}
else{
answer++; //기지국 설치
pos += 2*w+1;
}
}
return answer;
}
}
'알고리즘 공부 및 문제 풀이 > 프로그래머스(PRO)' 카테고리의 다른 글
[pro] 프로그래머스 level3 12904 가장 긴 팰린드롬 (Java) (0) | 2023.01.30 |
---|---|
[pro] 프로그래머스 level3 12938 최고의 집합 (Java) (0) | 2023.01.27 |
[pro] 프로그래머스 level3 12927 야근 지수 (Java) - 우선순위 큐 (0) | 2023.01.26 |
[pro] 프로그래머스 level3 17676 추석 트래픽 (Java) (0) | 2023.01.26 |
[pro] 프로그래머스 level3 17678 셔틀버스 (Java) - 우선순위 큐 (0) | 2023.01.25 |