(Python/LV3) 기지국 설치

728x90

문제출처: 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

아이디어 기지국이 설치된 아파트 주변만 고려한다.