C# 기지국 설치 / 프로그래머스 [Lv.3]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12979

 

 

나의 풀이

public int solution(int n, int[] stations, int w)
{
    int answer = 0;
    int width = (w * 2 + 1);

    // station을 순회하면서 station의 범위에 닿지않은 chunk를 범위로 나눠준다.
    int index = 1;
    foreach(int s in stations)
    {
        int chunkCount = (s - w) - index;
        if(chunkCount > 0)
            answer += (chunkCount + width - 1) / width;

        index = s + w + 1; // 전파 범위가 끝나는 지점으로 밀어준다.
    }

    // 루프가 끝난 후에 끝단에 남아있는 청크를 처리한다.
    int ramain = n + 1 - index;
    if(ramain > 0)
        answer += (ramain + width - 1) / width;

    return answer;
}

station 컬렉션을 순회하면서 좌측 전파범위 직전까지(전파가 안닿는 위치까지의) 아파트 갯수를 세고,

필요한 만큼 새로운 기지국을 세운 후, 우측 전파범위로 포인터를 옮기는 방식으로 처리. 

 

최대 갯수가 정해져있는 경우 그룹의 개수는 Ceiling Division 이라는 방식으로 계산하면 한번에 계산된다.

// 두번 계산함
answer += chunkCount / width;
answer += chunkCount % width > 0 ? 1 : 0;

// 한번에 계산됨
answer += (chunkCount + width - 1) / width;

 

다른 사람 풀이

public int solution(int n, int[] stations, int w)
{
    int answer = 0;
    int station = 0;
    int now = 1;
    while (now <= n)
    {
        if (station < stations.Length && now >= stations[station] - w)
        {
            now = stations[station] + w + 1;
            station++;
        }
        else
        {
            now += w + w + 1;
            answer++;
        }
    }
    return answer;
}

나는 전파가 안닿는 청크를 만들고 나눴는데, '나누기는 덧셈의 반복문' 의 개념으로 풀이한 방식.