hackerland-radio-transmitters.py

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'hackerlandRadioTransmitters' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY x
#  2. INTEGER k
#

def hackerlandRadioTransmitters(x, k):
    if len(x) == 1:
        return 1
    # Write your code here
    x.sort()
    transmitters = 0
    
    idx = 0
    while idx < len(x):
        transmitters += 1
        # 설치했을 때 영향받는 범위 계산
        distance = x[idx] + k
        # 범위 안쪽에 있다면 신규 transmitter 설치할 필요가 없다
        while idx < len(x) and x[idx] <= distance:
            idx += 1
        # 설치한 위치에서 갈 수 있는 최대 범위는 idx-1. 여기에 설치하면 왼쪽 범위는 전부 커버된다.
        # 만약 여기에 transmitter를 설치하면, 오른쪽으로는 추가로 어디까지 뻗어가는지 계산.
        distance = x[idx-1] + k
        while idx < len(x) and x[idx] <= distance:
            idx += 1
                
    return transmitters
    
                
    
    
        
    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    x = list(map(int, input().rstrip().split()))

    result = hackerlandRadioTransmitters(x, k)

    fptr.write(str(result) + '\n')

    fptr.close()