문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/12979
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이:
import math
def solution(n, stations, w):
count = 0
maps = [0 for _ in range(n)]
for station in stations:
for i in range(station - w - 1, station + w):
if i >= 0 and i < len(maps):
maps[i] = 1
result = []
zeros = []
answer = 0
for i, num in enumerate(maps):
if num == 0:
zeros.append(i)
elif len(zeros) > 0:
result.append(zeros)
zeros = []
if len(zeros) > 0:
result.append(zeros)
for i in range(len(result)):
# 연속된 범위를 고려하여 필요한 기지국의 개수 계산
answer += math.ceil(len(result[i]) / (2 * w + 1))
return answer
정확성 다 맞고 / 효율성 다 틀림,,
일단 틀렸지만 기록을 위해 설명한다.
내가 생각한 아이디어는 0이 반복된 곳에 인덱스를 리스트로 저장해서 리스트 별로 필요한 지점 갯수를 더하면 되는것이다.
그래서 첫 이중포문으로 [0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1] 이렇게 만들어주고
이거를 돌면서 만약에 0 이면 리스트에 담아둔다
만약에 1이 나오면 지금까지에 0 을 추가하는 것이다. 맨 마지막에 0 이면 그거는 추가가 안되므로 if문으로 남은것도 추가
그리고 범위에서 w에 왼쪽 오른쪽으로 니깐 * 2 해주고 자기자신 더해줘야하니깐 그걸로 나눠준 갯수가 필요한 갯수인것이다.
근데 틀렸다. 고쳐본다
def solution(n, stations, w):
res, now, idx = 0, 1, 0 # 정답값, 현재 아파트 번호, 기지국 인덱스
while now <= n:
# 기지국 범위 안에 포함되는 경우이다. 1, 4 - 1
if idx < len(stations) and now >= stations[idx] - w:
now = stations[idx] + w + 1 #아파트 번호는 기지국 바로 옆으로 이동
idx += 1 #다음 기지국으로 이동
else: # 포함이 안된경우 기지국 설치
now += w * 2 +1
res += 1
return res
아이디어 기지국이 설치된 아파트 주변만 고려한다.
이걸로 하면 else 에 들어 가기때문에
현재 아파트 번호가 1*2+1 인 4가 되고
현재 아파트 번호인 4가 stations[idx] - w 에 못 들어갔기 때문에 한번더 else 문 작용한다.
그럼 아파트 번호는 7이 돼서 기지국 범위 안에 포함된다. 그러면 설치 안 해도 되니깐 기지국 밖으로 이동해야하니깐,
기지국에서 + w+1 만큼이동하면 12으로 이동되어있다.
쭉 반복 하면 다음 now는 15 그다음은 19인데 n보다 크니깐 while문 종료후 나온다.
댓글