[알고리즘] 프로그래머스 - 기지국 설치

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

효율성 통과 실패한 내 풀이 1

def solution(n, stations, w):
    houses = [False] * n

    for station in stations:
        for i in range(station-w-1, station+w):
            if 0 <= i < n:
                houses[i] = True

    count = 0
    for i in range(n):
        if houses[i] == False: # 전파가 안닿으면
            count += 1
            if i + w >= n:
                for j in range(i, i+w+1):
                    if j >= n:
                       break
                    houses[j] = True
            else:
                next_point = i + w
                for j in range(next_point - w, next_point + w +1):
                    if j >= n or j < 0:
                        continue
                    houses[j] = True
    # print(houses)
    return count

N은 최대 200,000,000이고, w는 최대 10,000이니 당연히 실제 시뮬레이션을 하면 효율성 통과를 못한다.

효율성 통과한 내 풀이 2

import math
from itertools import combinations
from collections import deque
import sys
import heapq as hq

def solution(n, stations, w):
    house_counts = []
    cur_pos = 1
    for station in stations:
        if cur_pos < station -w:
            house_counts.append(station-w - cur_pos)
            cur_pos = station + w + 1
        else:
            cur_pos = station + w + 1

    if cur_pos <= n:
        house_counts.append(n-cur_pos+1)

    answer = 0
    for zone in house_counts:
        answer += int(math.ceil(zone / (2*w +1)))
    return answer

stations가 주어지니, 전파가 닿지 않는 곳이 몇개씩 있는지 계산해서 house_counts에 저장한다. 그다음 각 house_counts의 요소에 대해 몇 개의 기지국이 필요하는지 계산하는데 한 기지국당 2*w+1을 커버할 수 있다. math.ceil을 이용해서 소수점이 남으면 올려서 계산해준다.