-
[파이썬] 기지국 설치코딩 테스트/프로그래머스 2023. 4. 17. 19:39
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/12979
문제 풀이
- n의 최댓값이 2억인데 채점 시 효율성 테스트까지 거치므로 시간 복잡도는 O(n)을 넘으면 안됨
- n을 순회하기 보단 길이가 1만 이하인 stations를 활용해서 수학적으로 접근
- 한 지점에서 커버 하는 공간은 2*w + 1 이다. (좌우 + 자기 자신)
- 길이가 10이고 w가 1이면 10//3 을 통해 4개가 필요한 걸 알 수 있음
- stations이 이미 있으므로 이것을 제외하고 좌우를 생각
- 만약 stations이 차지하고 있는 왼쪽보다 1보다 작다면 왼쪽에는 추가 할 필요가 없음
- 기준점(start)에는 오른쪽 차지한 영역 이 후 값을 저장
- sations을 모두 정리했는데도 기준점이 n보다 작을 경우 남은 구간은 width로 나누면 됨(ceil을 통해 나머지가 있을 경우 자동으로 +1 해줌)
소스 코드
from math import ceil def solution(n, stations, w): answer = 0 width = w*2+1 start=1 for s in stations: answer+=max(ceil((s-w-start)/width),0) start=s+w+1 if n>=start: answer+=ceil((n-start+1)/width) return answer print(solution(11,[4,11],1))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[이분 탐색] 징검다리 건너기 (파이썬) (0) 2023.04.20 [투 포인터] 보석 쇼핑 (파이썬) (0) 2023.04.20 [2021 카카오 블라인드] 합승 택시 요금 (파이썬) (0) 2023.04.17 [탐색] 여행 경로 (python) (1) 2023.04.16 [그리드] 섬 연결하기 (python) (1) 2023.04.11