Level 3 기지국 설치 Python 3

https://programmers.co.kr/learn/courses/30/lessons/12979?language=python3 

코딩테스트 연습 - 기지국 설치

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_기지국설치.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from math import ceil
def solution(n, stations, w):
    answer = 0
    power = w*2+1
    left = stations[0]-w
    right = stations[0]+w
    if left > 1:
        answer += ceil(left/power)
    left = right+1
    for s in stations[1:]:
        right = s+w
        if left < s-w:
            answer += ceil((s-w-left)/power)
        left = right+1
    if right < n:
        answer += ceil((n-right)/power)

    return answer

---

풀이 과정

풀이 시간 1시간 30분

 기지국에 의해 전파되지 않는 왼쪽 또는 오른쪽 남은 아파트들이 있는지 파악하여 모두 전파 될 수 있도록 기지국을 추가로 설치해주는 방식으로 문제를 해결하였다. 가령 1부터 8까지의 아파트들이 전파되지 못했다면 기지국은 최소 ceil((8-1+1)/(2*w+1))개가 필요하다는 것을 몇 가지 경우를 손으로 그려보며 파악하였다. 따라서 stations 배열을 하나씩 탐색하면서 왼쪽 또는 오른쪽에 남은 아파트들에게 전파할 수 있도록 기지국을 설치해 나가면 되기 때문에 시간복잡도는 stations의 길이만큼 소요되므로 O(n)이다. 공간복잡도도 stations 길이만큼 소요되므로 O(n)이다.

from math import ceil
def solution(n, stations, w):
    answer = 0
    #기지국 전파 길이
    power = w*2+1
    #첫번째 기지국에 의해 전파된 첫번째 아파트
    left = stations[0]-w
    #첫번째 기지국에 의해 전파된 마지막 아파트
    right = stations[0]+w
    
    #왼쪽에 전파되지 않은 아파트가 있는 경우
    if left > 1:
        #왼쪽에 있는 아파트들에게 모두 전파할 수 있도록 기지국을 설치
        answer += ceil(left/power)
        
    #다음 아파트로 left 갱신
    left = right+1
    for s in stations[1:]:
        #현재 기지국 s에 의해 전파된 마지막 아파트를 right로 갱신
        right = s+w
        #현재 기지국 s가 왼쪽에 있는 아파트들에게 모두 전파하지 못한 경우
        if left < s-w:
            #왼쪽 남은 아파트들에게 전파할 수 있도록 기지국 설치
            answer += ceil((s-w-left)/power)
        #다음 아파트로 left 갱신
        left = right+1
    #마지막 기지국이 마지막 아파트까지 전파하지 못한 경우
    if right < n:
        #오른쪽 남은 아파트들에게 전파할 수 있도록 기지국 설치
        answer += ceil((n-right)/power)

    return answer
#시간복잡도 = O(n), 공간복잡도 = O(n)

---

오답 노트

처음에는 아파트 N개의 크기의 ck배열을 선언하여 기존의 기지국에 의해 전파가 되는지의 여부를 체크해주고, N-1번째 아파트부터 0번째 아파트까지 탐색하여 전파가 되지 않았다면 기지국을 설치해나가는 방식으로 알고리즘을 짰다. 그 결과 정확도는 다 맞았지만, 효율성에서시간 초과가 났다. 아무래도 아파트가 최대 2억개로 주어지기 때문에 첫번째 while문이 최악의 경우, n-1부터 0까지 반복하고 또 기지국 설치 위치를 찾아내는 두번째 while문까지 실행되면 시간초과가 날 수 밖에 없다.

#시간 초과
def solution(n, stations, w):
    answer = 0
    ck = [0]*n
    for s in stations:
        now_s = s-1
        ck[now_s] = True
        for i in range(1, w+1):
            if now_s-i >= 0: ck[now_s-i] = 1
            if now_s+i < n: ck[now_s+i] = 1

    i = n-1
    while i >= 0:
        if ck[i]: 
            i-=1
            continue
        dis = 0
        while dis < w and i-dis > 0:
            dis += 1
            if ck[i-dis]:
                dis -= 1
                break
        answer += 1
        i -= (dis+w+1)

    return answer