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

programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

 

 

ceil이 시간을 많이 잡아먹는다는 글을 봐서 그걸 고쳐주었으나...! 역시 시간초과가 떴다.

실패한 코드 (시간초과) → 전파가 닿지않는 아파트를 하나하나 배열에 추가해준 것이 문제였다!

def solution(n, stations, w):
    answer = 0

    apts = [0] * (n+1)
    for s in stations:
        # print(s)
        tmpStart = s-w
        tmpEnd = s+w
        if tmpStart < 1:
            tmpStart = 1
        if tmpEnd > n:
            tmpEnd = n
        for i in range(tmpStart, tmpEnd+1):
            apts[i] = 1 #전파 닿는곳은 1로 표시
    # print(apts)
    
    oneRange = 1 + (w * 2) #하나의 기지국이 닿는 범위, w가 자연수이므로 최소 3
    aptCnt = 0 
    for i in range(1, n):
        if apts[i] == 0:
            aptCnt += 1
            if apts[i+1] == 1 or i+1 == n:
                answer += aptCnt // oneRange
                if aptCnt % oneRange != 0:
                    answer += 1
                aptCnt = 0

    return answer

 

그래서 이를 어쩐다 하고 검색을 해보니 저렇게 리스트를 생성하지 않고, 전파가 닿지않는 거리만 계산해서 하신 분이 계셔서 그 방법으로 다시 풀어봤다.

 

🙋‍♀️작성한 코드

import math
def solution(n, stations, w):
    answer = 0

    noStations = [] #통신이 안되는 거리를 넣는 리스트
    noStart = 1 #전파가 닿지않는 시작점
    
    for s in stations:
        sStart = s - w #전파가 닿는 시작점
        sEnd = s + w #전파가 닿는 끝점
        
        if sStart - noStart > 0:
            noStations.append(sStart - noStart)
        noStart = sEnd + 1
    
    if noStart <= n:
        noStations.append(n+1 - noStart)
    # print(noStations)
    
    oneRange = 1 + (2 * w)
    for ns in noStations:
        answer += math.ceil(ns/oneRange)
        
    return answer