HackerRank [Search] Hackerland Radio Transmitters /알고리즘 해커랭크

문제 주소 : https://www.hackerrank.com/challenges/hackerland-radio-transmitters/problem

 

 

문제 :  1차원 배열의 마을에서 모든 집에 라디오가 들르게 하는데 필요한 송신기의 수

 

풀이

1. 시작점(nBefore)에서 최대로 멀리 세울 수 있는 안테나 위치(nPos)를 찾는다
2. 그 위치로부터 영향을 주는 최대거리(nAfter)를 찾는다 그리고 안테나 수(Antcnt) 값을 누적시킨다
3. 그 다음칸을 시작점으로 변경 후 위 작업을 반복하여 마을의 끝 위치에 도달하면 종료

답안

#!/bin/python3

import math
import os
import random
import re
import sys



# Complete the hackerlandRadioTransmitters function below.
def hackerlandRadioTransmitters(x, k):
    x.sort()
    nAntCnt = 0

    nPos = 0
    nBefore = 0
    nAfter = 1
    nXlen = len(x)

    if nXlen == 1:
        return 1

    while True:             
        if abs(x[nBefore] - x[nPos]) <= k:
            nPos += 1
            if nPos == nXlen:
                nAntCnt +=1                 
                return nAntCnt
            continue
        else:
            nAfter = nPos
            nPos -= 1
            
            while True:
                if abs(x[nAfter] - x[nPos]) <= k:
                    nAfter += 1                    
                    if nAfter == nXlen:                         
                        nAntCnt += 1       
                        return nAntCnt
                else:
                    nAntCnt += 1
                    nBefore = nAfter
                    nPos = nBefore                  
                    break                
    return nAntCnt            



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

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

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

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

    fptr.close()

 

느낀점

이 문제를 풀기 전 타임아웃을 많이 겪었었고 해당 문제 난이도가 Medium이기에 최대한 빠르게 처리하는 것도 관건이라 생각하여 안테나를 설치할 때마다 마을을 리스트로 잡아놓고 설치 후 잘라내며 했었는데
오히려 쓸데없는 리스트 처리로 속도가 더 느려져 타임아웃이 났었다

그냥 풀었다면 오히려 실수 없이 바로 풀었을 문제

자라보고 놀란 가슴 솥뚜껑 보고 놀란다... ㅠ