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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

n	stations	w
11	[4, 11]	1

 

- 기지국 하나 당 전파의 길이 : length = 2w - 1

+ 최적화 주의 ( 아파트 개수만큼 순회하게 되면 효율성 시간초과 )

 

풀이 순서

1. 전파가 닿지 않는 이어진 아파트의 개수를 구함

 - 전파가 닿지 않기 시작하는 인덱스를 담은 minList

 - 전파가 닿기 시작하는 인덱스를 담은 maxList

 -> 이어진 아파트 개수 : maxList - minList

 

2. 전파가 닿지 않는 이어진 아파트의 개수 내에 기지국을 몇개 새워야 하는지 구하여 모두 더함

- 각 그룹의 사이는 기지국으로 분리되어 있으므로 서로의 범위가 겹칠 일은 없음

-> 기지국 필요 개수 : 개수 / 전파길이 ( 나눈 나머지가 있을 경우 + 1 )

 

주석 참조

    using System;
    using System.Collections.Generic;

    class Solution
    {
        public int solution(int n, int[] stations, int w)
        {
            int answer = 0;
            int length = 2 * w + 1; // 전파 길이

            var minList = new List<int>(); // 전파가 닿지 않기 시작하는 인덱스 값
            var maxList = new List<int>(); // 전파가 닿기 시작하는 인덱스 값

            // 리스트에 값 세팅 (첫, 끝 부분 예외처리)
            minList.Add(1);
            for (int i = 0; i < stations.Length; i++)
            {
                minList.Add(Math.Max(stations[i] + w + 1, 0));
                maxList.Add(Math.Min(stations[i] - w, n + 1));
            }
            maxList.Add(n + 1);

            // 기지국이 필요한 개수 찾기
            for (int i = 0; i < minList.Count; i++)
            {
                // 이어진 아파트 개수
                int count = maxList[i] - minList[i];

                // 필요한 기지국 개수 카운트
                if (count > 0)
                    answer += count / length + ((count % length != 0) ? 1 : 0);
            }

            return answer;
        }
    }