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

문제보기

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

프로그래머스

 

풀이 & 코드

비교적 난이도가 낮은 문제다. 전에 말한 것 처럼 정답률 내림차순으로 풀고 있는 데 흠... 

기지국 설치

 

문제를 쪼개보자! 크게 두 개로 쪼갤 수 있다.

1) 기지국 설치가 필요한 곳을 구분해야 한다.  2) 각각의 구간에 필요한 기지국 개수의 최소는 몇개인가.

 

1번은 stations와 w를 계산하면 간단하게 구할 수 있다.

2번은 굳이 정하자면 greedy와 같다고 볼 수 있다. 그냥 앞에서 부터 기지국 범위를 최대로 설치하고 개수를 세면 된다. 

 

필자는 while문을 돌면서 1번을 해결했고 cal 함수를 통해 해당 구간에서 필요한 기지국의 최소 개수를 구했다.

def cal(n, i):
    return n // i + 1 if n % i else n // i

def solution(n, stations, w):
    answer = 0
    loc = 1
    interval = 2*w + 1
    while len(stations) != 0:
        s = stations.pop(0)
        if loc < s-w:
            num = s-w - loc
            answer += cal(num, interval)
        loc = s+w+1
    
    if loc < n+1:
        answer += cal(n+1 - loc, interval)
    
    return answer