프로그래머스 level3 기지국 설치 (python)

Problem

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

Solution

1차 풀이

def solution(n, stations, w):
    answer = 0
    stack = []
    curr_station = 0
    for i in range(1, n+1):
        # 마지막 기지국 이후
        if curr_station >= len(stations):
            stack.append(i)
        
        # i 보다 뒤에 있는 기지국 중 제일 가까운 기지국 범위 왼쪽
        elif i  < stations[curr_station] - w:
            stack.append(i)
            
        elif stations[curr_station] - w <= i <= stations[curr_station] + w:
            if stack:
                answer += len(stack) // (2 * w +1)
                if len(stack) % (2 * w + 1) > 0:
                    answer += 1
                stack = []
            if i == stations[curr_station] + w:
                curr_station += 1
        
    if stack:
        answer += len(stack) // (2 * w +1)
        if len(stack) % (2 * w + 1) > 0:
            answer += 1
        stack = []
                
    return answer

1부터 N까지 가면서 기지국 기준으로 계산하였다. N이 2억까지 가능하면서 시간 초과가 발생하였다.

2차 풀이

def solution(n, stations, w):
    answer = 0
    left = 0
    
    for station in stations:
        if left < station - w:
            answer += (station - w - left - 1) // (2 * w + 1)
            if (station - w - left - 1) % (2 * w + 1) > 0:
                answer += 1
        left = station + w
    
    if left <= n:
        answer += (n - left) // (2 * w + 1)
        if (n - left) % (2 * w + 1) > 0:
            answer += 1

    return answer

현재 위치를 left로 했을 때 기지국의 왼쪽 범위와 비교하여 세워야할 기지국에 개수를 구하였다.

현재 위치가 10이고 다음 기지국이 15에 있고 범위가 1이라 하면 해당 기지국은 14~16까지 전파가 가능하다. 10부터 14까지 커버하기 위해서는 10 / 3의 몫에다가 나머지가 존재한다면 1을 더해준 값만큼의 기지국이 필요하다