[프로그래머스/Python] Level 3_기지국 설치

📌문제 유형

Summer/Winter Coding(~2018), 그리디, 구현

 

📌문제

프로그래머스

 

 

📌나의 문제풀이

- 점수 : 93.3

• station별 전파 가능한 곳 min_s(가장 작은 값), max_s(가장 큰 값) 저장
• 이전 비어 있는 범위 range_에 저장
• 기지국 수 range_ / (2w+1) 올림한 값

from math import ceil

def solution(n, stations, w):
    answer = 0
    
    start = 0
    for station in stations:
        min_s, max_s = station - w, station + w
        range_ = min_s - start - 1

        answer += ceil(range_ / (2*w+1))
        start = max_s
    
    if start < n:
        range_ = n - start - 1
        answer += ceil(range_ / (2*w+1))

    return answer

 

-정답

• if start < n 구문에서 n이 포함되므로 range_의 -1 제외

from math import ceil

def solution(n, stations, w):
    answer = 0
    
    start = 0
    for station in stations:
        min_s, max_s = station - w, station + w
        range_ = min_s - start - 1
        
        # 범위 넘지 않도록 제한
        if min_s <= 0:
            range_ = 0
        # 범위 넘지 않도록 제한
        if range_ != 0:
            answer += ceil(range_ / (2*w+1))
            
        answer += ceil(range_ / (2*w+1))
        start = max_s
    
    if start < n:
        range_ = n - start
        answer += ceil(range_ / (2*w+1))

    return answer

 

📌다른사람의 문제풀이

- 방식 유사

def solution(n, stations, w):
    ans = 0
    idx = 0
    location = 1

    while(location <= n) :
        if(idx < len(stations) and location >= stations[idx]-w) :
            location = stations[idx]+w+1
            idx += 1
        else :
            location += 2*w+1
            ans += 1
    return ans