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

문제 링크

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

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

풀이 - 다른 블로그 참고 

• 풀이 과정이 이해가 안되서 좀 힘들었음.
• 이진 탐색으로 풀어야 하나 싶었는데, 그리디 문제에 더 가까웠음. 
• idx : 배열 stations의 인덱스 
• locate : 기지국 설치 위치 
  1. 기지국 설치 위치가 이미 기지국이 설치되어있는 station 전파의 도달 거리 안에 없다면, 기지국을 설치하고 다음 기지국 설치 위치를 현재 위치 + w*2 + 1(기지국 설치되어있는 곳) 로 옮김.
  2. station 전파의 도달 거리 안에 있다면, 해당 station의 최대 전파 도달 거리 위치로 다음 기지국 설치 위치를 옮기고, stations의 인덱스 하나 증가 
  3. stations의 인덱스가 마지막이라면 answer 하나 더 증가하고 끝나게 됨. 

• def solution(n, stations, w):
    answer = 0 
    # stations의 인덱스 
    idx = 0
    # 기지국 설치 위치 
    locate = 1
    
    while locate <=n :
    	# 전파 거리에 속하지 않거나, stations의 인덱스를 초과하였을 경우 
      if idx >= len(stations) or locate < stations[idx] - w :
        locate += w*2 + 1 
        answer += 1 
      # 전파 거리에 속할 때 
      else:
        locate = stations[idx] + w + 1
        idx += 1 
  
    return answer