프로그래머스 레벨 3 기지국 설치

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

이때, 우리는 5g 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

실패코드

import math
def solution(n, stations, w):
    answer = 0
    apt=[0]*(n+1)
    em_aptlist=[]
    for station in stations:
        try:
            apt[station-w]=-1
        except:
            apt[1]=-1
        try:
            apt[station+w+1]=1
        except:
            pass
    check=0
    for i in range(1,n):
        apt[i+1]+=apt[i]
        
    for i in range(1,n+1):
        if apt[i]<0:
            answer+=math.ceil(check/(2*w+1))
            check=0
        else:
            check+=1
    
    answer+=math.ceil(check/(2*w+1))
    return answer

꽤나 효율적으로 짰다고 생각했는데 효율성 테스트에서 모조리 시간초과가 떴음 (문제는 정확성 테스트도 4개 틀림 3,8,9,16,19,21....)
일단 정확성 테스트부터 통과하는것이 중요하니 정확성 부분을 고쳐주기로함

정확성 수정

    for station in stations:
        try:
            apt[station-w]=-1
        except:
            apt[1]=-1
        try:
            apt[station+w+1]=1
        except:
            pass

위 코드를 아래와 같이 수정해주었더니 3,8,9 제외 통과

    for station in stations:
        try:
            apt[station-w]-=1
        except:
            apt[1]-=1
        try:
            apt[station+w+1]+=1
        except:
            pass

마침내 아래처럼 바꿔주었더니 모든 정확성 테스트 통과

    for station in stations:
        if station-w<1:
            apt[1]-=1
        else:
            apt[station-w]-=1
        if station+w+1>n:
            continue
        else:
            apt[station+w+1]+=1

자꾸 정확성 테스트에서 실패했던 이유는 다음과 같았다
첫째로 apt[i]=-1이 아니라 apt[i]-=1을 해주어야함, 그래야 겹치는 부분 처리 가능
둘째로, 코드 작성에 실수가 있었음 맨 위의 try문을 살펴보면 station-w가 인덱스를 초과할때 apt[1]에 -=1을 해주는 부분인데, 이때 station-w이 0이 되면 오류로 처리되지 않아, apt[0]에 -=1을 처리해버림, 그러나 문제상에서 볼때 실질적 인덱스는 1부터 시작이므로, 0에 -=1이 되는것도 사실상 오류로 판단하고 apt[1]에 -=1을 해주어야 함

효율성 수정

지금 보면, 기존 코드는 n을 필연적으로 2번 순회할 수 밖에 없는 구조임,o(n)이라고 하더라도, n의 최댓값이 2억이기 때문에 효율성 측면에서 많이 부담이 될 수 밖에 없다. 따라서 n을 한번만 순회할 수 있는 코드로 바꾸어 주어야함.
따라서 효율성을 수정하기 위해서는 코드를 뒤집어 엎어야함ㅠ 아쉽지만 ㅂㅂ

그리디 알고리즘을 활용하여 풀 수있음.

현재 기지국과 다음 기지국의 범위가 겹치면, 범위를 늘려줌 (s,e변수를 활용하여)
하지만 겹치지 않는다면? 현재 기지국의 끝점과 다음 기지국의 시작점의 차이를 계산하고, 필요한 기지국의 갯수를 answer변수에 더해주면 됨.

가보자고

import math

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

    return answer

이렇게 했더니 효율성 테스트 모두 통과가 된다!! 하지만 정확성 테스트에서 반토막 ㅠ

import math

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

    return answer

s=0으로 해줬더니 8,17 제외하고 모두 통과! 거의 다왔다

최종코드

import math

def solution(n, stations, w):
    answer = 0
    s = 1   # s를 전파가 도달하지 않는 마지막 위치라고 하자
    for station in stations:
        if station-w-s>=1:
            answer+=math.ceil((station-w-s)/(2*w+1))
        s=station+w+1
        
    if s<=n:
        answer+=math.ceil((n-s+1)/(2*w+1))
    return answer

효율성 정확성 모두 통과
이전의 코드가 틀렸던 이유는 바로
문제는 s의 초깃값 설정에 있었음

우리가 갱신해주는 s의 위치는 전파가 마지막으로 도달하는 위치임, 그러나 s의 초깃값을 보면 복불복임, 전파가 도달할 수도, 안할 수도 있다는 소리,

s가 0이든 1이든 s의 초깃값이 전파가 도달하지 않는 경우로 설정될때, 다음 s는 전파가 설정되는 값으로 설정되기 때문에 코드의 일관성이 없어지고 반례가 생기기 마련이다. 즉 해결방안으로는 초기에 반복문으로 들어가기전 s를 1로 설정해줌 이때 s는 전파가 도달하지 않는 곳임, 그후에도 s를 전파가 도달하지 않는 가장 나중의 곳으로 설정해줌으로써(station+w+1) 일관성을 지킬 수 있게 된다.

배운점
try except pass 문 쓸때, 에러 발생 조건 확실하게 판단하기

math.floor, math.trunc는 똑같이 내림 함수, 그러나 trunc는 0으로 양하게 내리는 반면 floor는 계속 내림
올림 함수는 math.ceil임
코드 일관성
초깃값의 일관성