[JAVA] Summer/Winter Coding(~2018) 기지국 설치

https://programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

 

커뮤러닝 STEP 1-1 문제!

개판쳐서 다시 풀어보았따!

---

풀이)

원래 제일 유명한 풀이 보고 이해하려고 했는데 너무 이해가 안가서 그냥 이해가는 풀이로 다시 풀어봄!

일단 이미 설치된 기지국 기준으로 탐색하는 거임

 

설치된 기지국 기준으로 전파 범위 시작, 끝 잡고 현재 위치 1부터 반복하면서 접근함

만약 현재 위치(cur)가 전파 범위 시작 위치(start)보다 작으면 전파 범위내에 없는 거니까 기지국을 설치해준다

설치 방법은 우선 현재 위치와 전파 범위 시작 위치를 빼서 전파가 없는 구간의 길이를 구한다 -> diff

그리고 그 범위를 전파 범위(range)로 나눠서 나머지가 0이면 딱 나눠떨어지는거니까 나눈 몫만큼 더해주고, 0이 아니면 기지국을 하나 더 설치해준다

그리고 현재 위치를 전파 끝 위치 + 1로 해준다 -> 다음 기지국 기준으로 탐색해야하니까!

 

위 for loop이 끝나면 이제 설치된 기지국 뒤를 봐줘야 한다

만약 설치된 마지막 기지국의 영향 범위가 끝난 뒤에가 있다면 거기에도 기지국을 설치해줘야 한다

그래서 현재위치(cur)와 n을 비교해서 cur이 작으면 뒤에 몇개를 설치할 건지 구해주면 된다

 

아래는 코드!

 

 

 

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int start = 0; // 기지국 시작
        int end = 0; // 기지국 끝
        int cur = 1; // 현재 위치
        int range = 2*w + 1; // 전파 범위
        int diff = 0;

        for(int i=0;i<stations.length;i++) { // 이미 설치된 기지국이 미치는 범위까지만 탐색
            start = stations[i]-w;
            end = stations[i]+w;
            if(cur < start) {
                diff = start - cur;
                if(diff % range == 0) {
                    answer += diff / range;
                } else {
                    answer += diff / range + 1;
                }
            }
            cur = end + 1;
        }

        if(cur <= n) { // 설치된 기지국 뒤에 전파 없는 범위 탐색
            diff = n - cur + 1;
            if(diff % range == 0) {
                answer += diff / range;
            } else {
                answer += diff / range + 1;
            }
        }
        return answer;
    }
}