[프로그래머스] 기지국 설치

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

프로그래머스

🤔 문제분석

처음에 문제를 접했을때 아래와 같은 방식으로 방법을 정하여 문제를 해결하였습니다.

1. 주어진 위치를 기준으로 기지국의 범위를 정한다.
2. 전파가 되지 않는 도시의 구간을 모두 구한다.
3. 도시의 구간의 길이를 구하여 기지국을 설치할 최소 수를 카운팅 한다.
   1. 설치할 최소 수 = 올림(도시의 길이 / w*2 + 1)

💻 코드

from math import ceil

def solution(n, stations, w):
    def make(city):
        return [max(0, city - w), min(city + w, n)]

    # 해당위치를 기준으로 기지국의 범위를 지정한다.
    temp = [[0, 0]] + list(map(make, stations)) + [[n+1, n+1]]
    n = len(temp)

    # 도시의 구간을 나눈다.
    city_range = set()

    # 겹치는 부분을 제거 해가면서 도시의 구간을 나누어본다.
    for i in range(1, n-1):
        if temp[i-1][1] < temp[i][0]:
            city_range.add((temp[i-1][1] + 1, temp[i][0] - 1))

        if temp[i+1][0] > temp[i][1]:
            city_range.add((temp[i][1] + 1, temp[i+1][0] - 1))

    answer = 0

    # 도시의 구간을 길이를 구하여 기지국을 설치할 최소 수를카운팅 한다.
    for r in city_range:
        length = r[1] - r[0] + 1
        answer += ceil(length / (1 + w*2))

    return answer

다른 사람의 풀이를 참조하였는데 저처럼 구간을 필터링 하지않고 주어진 조건 그대로 문제를 해결하여서 똑같이 구현 해보았습니다. 문제를 푸는 원리는 똑같으나 훨씬 간결합니다.

import math

def solution(n, stations, w):
    answer, start = 0, 1
    # 전파가 안되는 마을의 구간을 구한다.
    for cur in stations:
        length = cur - w - start
        answer += math.ceil(length / (w*2 + 1))
        start = cur + w + 1

		# 끝까지 안닿았을경우 갱신해준다.
    if n >= start:
        length = n + 1 - start
        answer += math.ceil(length / (w * 2 + 1))

    return answer