Daily Study Logging24 - 프로그래머스 기지국 설치
May 20, 2020
문제의 조건 대로 구현하기 위해 함수를 길…게 짜 보았지만, 효율성은 통과하지 못했다. 그래도 나름 깔끔하게 코드를 짰다는 점에서 스스로에게 조금의 칭찬은 해 주고 싶다.
시간초과 난 코드
from collections import defaultdict
index = 0
cnt = 0
def checkStation(n, station, w, visit):
if station - w > 0:
left = station - w
else:
left = 0
if station + w <= n :
right = station+w
else:
right = n
for i in range(left, right+1):
visit[i] = right+1
# print(visit)
# 해당 지점에서 출발 했을 때, 0이 아닌 지점을 반환해 주는 함수
def checkIfPossible(idx, visit, footprint, n):
global index
# print(idx)
if idx >= n:
return
if visit[idx] != 0:
tmp = footprint[:]
tmp.append(idx)
checkIfPossible(visit[idx], visit, tmp, n)
else:
print(footprint)
print(visit)
print(idx)
for i in footprint:
visit[i] = idx
# print(visit[i])
index = idx
# 0이 아닌 곳이 주어졌을 때 기지국을 건설하는 함수
def buildStation(index, visit, w, n, iterCnt):
global cnt
if iterCnt > w:
return
if index+w <= n and visit[index+w] == 0:
checkStation(n, index+w, w, visit)
cnt += 1
else:
buildStation(index-1, visit, w, n, iterCnt +1 )
def solution(n, stations, w):
global index, cnt
visit = defaultdict(lambda : 0)
for station in stations:
checkStation(n, station, w, visit)
while index <= n:
# index는 visit에서 0 인 것만 가르킨다.
checkIfPossible(index, visit, [], n)
# 0인 자리를 시작으로 타워를 지어서 0을 채운다.
buildStation(index, visit, w, n, 0)
index += 1
return cnt
print(solution(16, [9], 2))
하지만,효율성을 통과할 아이디어가 나지 않아 다른 사람의 코드를 참고했더니…생각을 조금만 바꾸면 매우 쉬운 문제였다는 사실을 깨닳았다.
import math
def solution(n, stations, w):
result = 0
distance = []
# 설치된 기지국 사이에 전파가 닿지 않는 거리를 저장한다
for i in range(1, len(stations)):
distance.append((stations[i]-w-1) - (stations[i-1]+w))
# 맨 앞 기지국에서 첫 번째 아파트 사이에 전파가 닿지 않는 거리,
# 맨 뒤 기지국에서 마지막 아파트 사이에 전파가 닿지 않는 거리를 저장한다
distance.append(stations[0]-w-1)
distance.append(n - (stations[-1]+w))
for i in distance:
# 닿지 않는 거리가 0 이하일 경우 스킵한다
if i <=0: continue
# 닿지 않는 거리에 설치할 수 있는 최소개수를 더해준다.
result += math.ceil(i / ((w*2) +1))
return result
빈 공간의 길이를 구하고 그 길이를 매꾸기 위한 타워 개수만 구하면 되는 것.
카카오코테를 오래 준비하다 보니, 아이디어를 좋게 하는 것 보다 구현을 하는 것에 더 집중을 했다. 카카오는 번뜩이는 아이디어로 풀기 보다는 복잡한 구현을 잘 해내도록 유도하는 문제를 내곤 하기 때문이다.
다른 코테에서는 간단한 방법이 있을 수 있음을 인지하고 풀도록 해야겠다.