개발/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 : 기지국 설치 위치
- 기지국 설치 위치가 이미 기지국이 설치되어있는 station 전파의 도달 거리 안에 없다면, 기지국을 설치하고 다음 기지국 설치 위치를 현재 위치 + w*2 + 1(기지국 설치되어있는 곳) 로 옮김.
- station 전파의 도달 거리 안에 있다면, 해당 station의 최대 전파 도달 거리 위치로 다음 기지국 설치 위치를 옮기고, stations의 인덱스 하나 증가
- 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