[코딩테스트] 프로그래머스 - 기지국 설치(Java, Level3)

안녕하세요.

와우 날씨가 정말 춥네요~

모두 감기 조심하시길 바랍니다.

 

이 문제는 +10점이나 주네요~

너무 기분좋습니다.

 

그렇다면 언제나 그렇듯 문제~코드~제가 생각한 로직 순으로 이어나가보겠습니다.

 

문제 만나보시죠~

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

프로그래머스

 

다음은 제가 작성한 코드입니다.

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        int w_=w*2+1;
        int dif=0;
        int div=0;
        int rest=0;
        
        dif=stations[0]-1-w;
        if(dif>=0)
        {
            div=dif/w_;
            rest=dif%w_;
        
            if(rest>0)
                answer=div+1;
            else
                answer=div;
        }
             
        for(int i=0;i<stations.length-1;i++)
        {
            dif=stations[i+1]-stations[i]-2*w-1;
            if(dif>=0)
            {
                div=dif/w_;
                rest=dif%w_;
        
                if(rest>0)
                    answer+=div+1;
                else
                    answer+=div;
            }
        }
        if(stations.length>0)
        {
            dif=n-stations[stations.length-1]-w;
            if(dif>=0)
            {
                div=dif/w_;
                rest=dif%w_;
            
                if(rest>0)
                    answer+=div+1;
                else
                    answer+=div;
            }
        }       
        return answer;
    }
}

다음은 제가 생각한 로직에 대한 설명입니다.

제가 생각한 로직은

범위별로 나누고자 했습니다.

 

case 1) 1번째 부터 특정 첫 번째 특정 범위 사이

case 2) 첫 번째 특정 범위 부터 두 번째 특정범위, 두 번째 특정 범위부터..  n번째 특정범위

case 3) n 번째 특정 범위부터 마지막 사이

 

이렇게 경우의 수를 나눴습니다.

 

다음은 해당 범위의 순수 빈 공간만을 구해보겠습니다.

case 1) 에서는 (0~ w...w위성) 이런 구조이기에 -w만큼 빼주고 위성도 빼 순수 빈공간만을 구하겠습니다.

case 2) 에서는 (시작점 위성w..w~~~w..w다음의 위성) 이런구조기에 -2*w와 -1을 해주겠습니다.

case 3) 에서는 (시작점 위성w..w~ 마지막) 구성이기에 -2를 해줬습니다.

 

그럼이제 빈공간에 위성을 꽂으면 됩니다.

가로수 심기랑 비슷하다고 생각하시면 쉬울 듯합니다.

 

w_인 간격은 위성+우측w+좌측w로 즉 2*w+1이 길이가 되겠습니다.

그럼이제 남은공간에 대해/w_로 계산하고 나머지가 있으면 +1을해주면 되겠습니다.

(+1은 나머지 공간은 겹치더라도 서로 통신을 위해 꽂아줘야 하기 때문입니다.)

 

네~ 이런 원리로 풀었습니다.

여전히 말로 설명하는건 어렵네요. 원래 말로 설명할 줄 알아야 진짜로 이해한거라는데..

오늘 코딩테스트는 여기까지입니다.

 

모두 좋은 하루 보내시길 바랍니다. :D

감사합니다.