[프로그래머스] 기지국 설치

내 실력 부족으로 카카오 문제보다는 다른 문제를  차근차근 풀고 있다.

오늘 풀 문제는 기지국 설치를 해주는 문제이다.

 

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

시간 복잡도가 미쳐있다... 문제 푸는데 1시간 반이 걸렸다 이렇게 오래 걸린 이유가 있다....ㅠ

 

문제 설명

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

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

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설치할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

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

 

제한사항

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

 

입출력 예

N	stations	W	answer
11	[4, 11]	1	3
16	[9]	2	3

N은 집의 개수, Stations은 기지국이 설치된 위치, W은 커버리지, answer는 커버리지 안에 못 들어온 집들에 기지국을 설치해주기 위한 최소한의 개수이다. 

문제 자체는 굉장히 쉽다. 중간의 빈 곳의 길이에서 몇 개 들어갈지만 정해서 다 더하면 되는 문제이다. 

하지만 여기서 큰 골칫거리가 있는데 범위다.... 범위가 200,000,000이나 된다...

처음 풀 때 200,000,000? 리스트로 풀면 괜찮지 않을까? 하고 풀었다가 시간 초과나 당황했다. 

그렇게 풀이를 3번 바꾸고 겨우 시간 초과를 면했다!

 

풀이 방법

고민 고민하다 아래 그림과 같은 방법을 사용했다.

Stations리스트 값-w와 Station리스트 값+w를 이용하여 길이 구하는 방법을 선택했다.

그리고 길이에 대한 기지국의 최소 설치 개수는 길이/((w*2)+1)의 올림으로 설정했다.

원래는 나머지 없이 떨어지면 그냥 길이//((w*2)+1), 나머지가 있으면 길이//((w*2)+1)+1로 했는데 생각해보니 해당 개념이 올림이었다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

왜?

처음 풀었을 때 리스트를 이용했는데 리스트를 이용하는 순간 시간 초과가 뜬다.  테스트를 해보니 O(n)이 넘어가면 시간 초과가 발생했다. 리스트를 N의 길이만큼 도는 것 만으로 시간 초과가 났다. 결국 리스트 없이 사용할 방법을 찾았고 stations를 돌면서 값을 처리하는 방법이 가장 빨라서 해당 방법을 적용했다.

 

코드

import math#올림 내장함수를 쓰기 위한 모듈
def solution(n, stations, w):
    answer = 0
    length=(2*w)+1#기지국의 커버리지 길이
    value=0#연산을 위한 value            
    for i in stations:#주어진 Stations리스트 돌기.
        if i-w<=1:#만약 i-w이 0보다 작으면 그냥 값을 1로 정의 
            a=1
        else:
            a=i-w
        answer+=math.ceil((a-value-1)/length)
        if i+w>=n:# 만약 i+w의 값이 n과 같거나 크면 n으로 정의
            value=n
        else:
            value=i+w
    else:
        answer+=math.ceil((n-value)/length)#여기는 돌다가 뒤에 남은 빈 집들의 연산을 위해 존재.
    return answer

 

실행 결과