문제 조건

input

• 아파트의 개수 n
  • 1 ≤ n ≤ 200,000,000
• 기지국이 설치된 아파트 stations 배열
  • 1 ≤ stations ≤ 10,000
• 기지국의 커버 범위 w
  • 1 ≤ w ≤ 10,000

output

• 최소 기지국 개수

문제 해석

• 그리디
  • 시간 복잡도 O(station.len)
  • stations를 순회하면서 커버 안 된 범위를 체크
    • 해당 범위에 필요한 기지국 개수를 +
  • stations을 모두 순회하고도 아파트가 남아있다면, 추가 처리

코드

def solution(n, stations, w):    
    cnt = 0
    # 현재까지 커버된 아파트의 마지막 인덱스
    convered_index = 0
    
    # 기지국이 설치된다면 커버 가능한 범위
    coverage = (w * 2) + 1
    
    for s in stations:
		    
		    # convered_index에서 기지국이 이미 설치된 s까지 커버해야하는 개수
        uncovered = s-w-convered_index -1
        
        # 기존 기지국으로 커버가 불가능하다.
        if uncovered > 0:
            cnt += uncovered // coverage
            
            # 나머지가 0이 아니면, 1개 추가로 설치
            if uncovered % coverage:
                cnt += 1
        
        # s+w까지는 모두 커버        
        convered_index = s + w
    
    # stations의 마지막 station까지 확인 후
    # 여전히 커버되지 않은 아파트가 남아있다면,
    if convered_index < n:
        uncovered = n - convered_index
        cnt += uncovered // coverage
        
        if uncovered % coverage:
            cnt += 1
        
    return cnt