Daily Study Logging24 - 프로그래머스 기지국 설치

from collections import defaultdict
index = 0
cnt = 0

def checkStation(n, station, w, visit):
    if station - w > 0:
        left = station - w
    else:
        left = 0
    if station + w <= n :
        right = station+w 
    else:
        right = n
    for i in range(left, right+1):
        visit[i] = right+1
    # print(visit)

# 해당 지점에서 출발 했을 때, 0이 아닌 지점을 반환해 주는 함수 
def checkIfPossible(idx, visit, footprint, n):
    global index
    # print(idx)
    if idx >= n:
        return
    if visit[idx] != 0:
        tmp = footprint[:]
        tmp.append(idx)
        checkIfPossible(visit[idx], visit, tmp, n)
    else:
        print(footprint)
        print(visit)
        print(idx)
        for i in footprint:
            visit[i] = idx
            # print(visit[i])
        index = idx
    
        
# 0이 아닌 곳이 주어졌을 때 기지국을 건설하는 함수 
def buildStation(index, visit, w, n, iterCnt):
    global cnt
    if iterCnt > w:
        return 
    if index+w <= n and visit[index+w] == 0:
        checkStation(n, index+w, w, visit)
        cnt += 1
       
    else:
        buildStation(index-1, visit, w, n, iterCnt +1 )
    
def solution(n, stations, w):
    global index, cnt
    visit = defaultdict(lambda : 0)
    for station in stations:
        checkStation(n, station, w, visit)
    
    while index <= n:
        # index는 visit에서 0 인 것만 가르킨다.
        checkIfPossible(index, visit, [], n)
        # 0인 자리를 시작으로 타워를 지어서 0을 채운다.
        buildStation(index, visit, w, n, 0)
        index += 1
    
    return cnt
        
print(solution(16, [9], 2))    

import math
def solution(n, stations, w):
    result = 0
    distance = []
    
    # 설치된 기지국 사이에 전파가 닿지 않는 거리를 저장한다
    for i in range(1, len(stations)):
        distance.append((stations[i]-w-1) - (stations[i-1]+w))
    
    # 맨 앞 기지국에서 첫 번째 아파트 사이에 전파가 닿지 않는 거리,
    # 맨 뒤 기지국에서 마지막 아파트 사이에 전파가 닿지 않는 거리를 저장한다
    distance.append(stations[0]-w-1)
    distance.append(n - (stations[-1]+w))
    
    for i in distance:
        # 닿지 않는 거리가 0 이하일 경우 스킵한다
        if i <=0: continue
        # 닿지 않는 거리에 설치할 수 있는 최소개수를 더해준다.
        result += math.ceil(i / ((w*2) +1))
    return result