문제
https://programmers.co.kr/learn/courses/30/lessons/12979
코딩테스트 연습 - 기지국 설치
N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5
programmers.co.kr
풀이
- N: 200,000,000 이하의 자연수
- stations의 크기: 10,000 이하의 자연수
- stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
- W: 10,000 이하의 자연수
시간 초과에 유의해서 풀어야 한다. N이 2억개이므로, N으로 순회를 한다면 시간초과가 발생한다.
station정보가 이미 정렬되어 있기 때문에 차례대로 순회하면서
커버가 되지 않는 영역을 찾아서 coverage수로 나눠주었다. (나머지가 있는 경우 +1)
나의 경우는 세 가지 경우로 나누어서 기지국 개수를 구하였다.
1. 이미 설치된 첫 기지국의 커버리지가 첫 번째 아파트를 포함하지 않는 경우
: 해당 기지국이 커버하는 첫 번째 영역 기준으로 이전을 분리하여 설치해야 할 기지국 개수를 구한다.
2. 현재 기지국이 커버하는 첫 번째 영역 - 이전 기지국이 커버하는 마지막 영역 > 0 보다 클 경우
: 두 기지국 사이에 커버하지 않는 영역이 있는 것이므로 해당 영역을 분리하여 설치해야 할 기지국 개수를 구한다.
3. 마지막 기지국의 마지막 영역이 N이 미만인 경우
: 마지막 부분에 커버되지 않은 부분이 있으므로 N-마지막 기지국의 마지막 영역을 분리하여 기지국 개수를 구한다.
소스코드
class Solution {
public int solution(int n, int[] stations, int w) {
int answer = 0;
int prev = 0, cur = 0;
int cover = 2*w + 1;
for(int i = 0 ; i < stations.length; i++) {
if(i == 0){
if(stations[i] - w > 1) answer += calc(stations[i] - w -1, cover);
prev = stations[i] + w;
continue;
}
cur = stations[i] - w;
if(cur - prev > 0) answer += calc(cur - prev -1, cover);
prev = stations[i] + w;
}
if(prev < n) answer += calc(n - prev, cover);
return answer;
}
public int calc(int seg, int cover){
return (seg%cover == 0) ? seg/cover : seg/cover + 1;
}
}
'💡Problem Solving > Programmers' 카테고리의 다른 글
[프로그래머스] 땅따먹기 (Java) (0) | 2021.11.09 |
---|---|
[프로그래머스] 정수 삼각형 (Java) (0) | 2021.11.09 |
[프로그래머스] 가장 먼 노드 (Java) (0) | 2021.11.06 |
[프로그래머스] 등굣길 (Java) (0) | 2021.11.05 |
[프로그래머스] 경주로 건설 (Java) (0) | 2021.11.05 |