[프로그래머스] 파이선 문제풀이 - 기지국 설치

첫 풀이

1.  n 길이의 배열을 만들어 전파가 터지는곳이면 0 안터지면 -1을 저장한다

2. 전파가 터지지 않는 구간을 찾아 전파의 범위로 나눈다

def solution(n, stations, w):
    cnt=0
    answer = [-1 for _ in range(n+1)]
    no=[]
    for i in stations:
        answer[i]=0
        for j in range(1,w+1): 
            if i-j>=1:
                answer[i-j]=0
            if i+j<len(answer):
                answer[i+j]=0
    flag=0
    for i in range(1,len(answer)):
        if flag==0 and answer[i]==-1:
            flag=1
            start=i
        elif flag==1 and answer[i]==0:
            end=i-1
            flag=0
            no.append([start,end])
        if i==len(answer)-1:
            if flag==1 and answer[i]==-1:
                end=i
                no.append([start,end])
    print(no)
    for a,b in no:
        total=b-a+1
        
        if total/(w*2+1)!=int(total/(w*2+1)):
            cnt+=int(total/(w*2+1))+1
        else:
            cnt+=int(total/(w*2+1))
        

    return cnt

정확도에서는 통과했지만 효율성에서는 꽝이였다

 

N이 최대 200,000,000 이하의 자연수라 배열로 사용하게 되면 메모리 사용이 커진다

더 나은 답안

1. n을 건들이지않고 stations을 직접 탐색한다

2. 인덱스를 사용하여 전파가 터지지 않는곳을 구하고 전파의 범위로 나눈다

 

import math
def solution(n, stations, w):
    ran=w*2+1
    cnt=0
    idx=1
    for s in stations:
        if s-w>0:
            cnt+=math.ceil((s-w-idx)/ran)
        idx=s+w+1
    if idx-1<n:
        cnt+=math.ceil((n-idx+1)/ran)
        
    return cnt

 

배운 점

1. n의 범위가 크면 배열을 사용하지않는 방법을 생각해야한다