개발/algorithm

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

zzi_on2 2022. 1. 11. 13:28

문제 링크

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

 

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

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5

programmers.co.kr

풀이 - 다른 블로그 참고 

  • 풀이 과정이 이해가 안되서 좀 힘들었음.
  • 이진 탐색으로 풀어야 하나 싶었는데, 그리디 문제에 더 가까웠음. 
  • 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