프로그래머스 - 기지국 설치 (Summer / Winter Coding ~ 2018) / Level 3

문제 : https://programmers.co.kr/learn/courses/30/lessons/12979

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

 

풀이

from math import ceil

def solution(n, stations, w):
    answer = 0

    for i in range(len(stations)+1):
        if i == 0:  # 첫 아파트부터 첫번째 station까지의 구간
            answer += ceil((stations[i]-w-1) / (2*w+1))
        elif i == len(stations):  # 마지막 station부터 마지막 아파트까지의 구간
            answer += ceil((n-stations[i-1]-w) / (2*w+1))
        else:  # station과 station 사이.
            answer += ceil((stations[i] - stations[i-1] - (2*w) - 1) / (2*w+1))
    return answer

문제 제한조건을 보면 n의 최대 크기가 2억이다.

따라서 O(n)의 시간복잡도여도 전체 구간을 한 바퀴 탐색하기 힘들다.

따라서 처음엔 시간복잡도가 O(logn)인 이분 탐색을 떠올렸다.

 

그러나 문제에 대해 잘 고민해보면 n를 탐색하지 않고도 stations 배열만 탐색해도 문제를 풀 수 있다.

0~stations[0] / stations[i-1]~stations[i] / stations[len(station)+1]~n 

위와 같이 3가지 경우의 수에 대하여 최소 기지국 수가 나오도록 계산식을 도출해내면

계산을 통해 stations (최대 길이 10,000 )배열만 탐색해도 문제를 해결할 수 있다.