[Level 3] 기지국 설치

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

프로그래머스

▶ 코드 (시간초과 -> 배열 업데이트 O)

def solution(n, stations, w):

    t = [0]*(n+1)
    
    # (1) 주파수 닿는곳 1로 표기   ->  시간복잡도 : O(n^2)  (N은 200,000,000 이하의 자연수)
    for st in stations:
        for i in range(st-w, st+w+1):
            if i < len(t):
                t[i] = 1
    #print(t)

    # (2) 0으로만 이루어진 집합 각각의 0개수 구하기
    c_arr = []
    c = 0
    for i in range(1, len(t)):
        if t[i] == 0:
            c+=1
            if i == len(t)-1:
                if c>0:
                    c_arr.append(c)
        else:
            if c>0:
                c_arr.append(c)
            c = 0
    #print(c_arr)

    # (3) 계산 
    answer = 0
    signal = 2*w + 1 # 주파수 대역 
    for a in c_arr:
        q = a//signal
        r = a%signal
        if r == 0:
            answer +=q
        else:
            answer += (q+1)
    #print(answer)
    return answer
        

#solution(11, [4,11], 1)
#solution(16, [9], 2)

 

▶ 코드 (정답 -> 배열 업데이트 X)

def solution(n, stations, w):
    dist = [] # 거리 집합 

    # (1) 설치된 기지국들 사이에 전파가 닿지 않는 거리를 저장한다.
    for i in range(1, len(stations)):
        dist.append( (stations[i]-w-1) - (stations[i-1]+w)  )

    # (2) 첫번째 아파트 ~ 맨 앞 기지국 사이에 전파가 닿지 않는 거리를 저장한다.
    dist.append( stations[0]-w-1 )

    # (3) 맨 뒤 기지국 ~ 마지막 아파트 사이에 전파가 닿지 않는 거리를 저장한다.
    dist.append( n - (stations[-1]+w)  )
    #print(dist)

    # (4) 계산 
    answer = 0
    signal = 2*w + 1 # 주파수 대역 
    for a in dist:
        q = a//signal
        r = a%signal
        if r == 0:
            answer +=q
        else:
            answer += (q+1)
    #print(answer)
    return answer

#solution(11, [4,11], 1)
#solution(16, [9], 2)

# 출처 : https://inspirit941.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%B0%EC%A7%80%EA%B5%AD-%EC%84%A4%EC%B9%98-Level-3