기지국 설치

기지국 설치
Summer/Winter Coding(~2018)
899명 완료

레벨3 중 쉬운 편
리스트을 안쓰는 방법으로... 

https://programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

시뮬레이션

def solution(n, stations, w):
    apartments = [False] * n
    for station in stations:
        for i in range(station - w - 1, station + w):
            if 0 <= i < n:
                apartments[i] = True
    gaps = []
    counter = 0
    for apartment in apartments:
        if apartment is False:
            counter += 1
        else:
            if counter != 0:
                gaps.append(counter)
            counter = 0
    if counter != 0:
        gaps.append(counter)
    width = w * 2 + 1
    answer = 0
    for coverage in gaps:
        answer += coverage // width + (1 if coverage % width else 0)
    return answer

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.6MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.8MB)
테스트 4 〉	통과 (0.04ms, 10.6MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.04ms, 10.7MB)
테스트 8 〉	통과 (0.04ms, 10.8MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.03ms, 10.7MB)
테스트 11 〉	통과 (0.04ms, 10.8MB)
테스트 12 〉	통과 (0.04ms, 10.8MB)
테스트 13 〉	통과 (0.04ms, 10.6MB)
테스트 14 〉	통과 (0.04ms, 10.8MB)
테스트 15 〉	통과 (0.04ms, 10.7MB)
테스트 16 〉	통과 (0.05ms, 10.6MB)
테스트 17 〉	통과 (0.04ms, 10.6MB)
테스트 18 〉	통과 (0.05ms, 10.7MB)
테스트 19 〉	통과 (0.05ms, 10.7MB)
테스트 20 〉	통과 (0.05ms, 10.8MB)
테스트 21 〉	통과 (0.06ms, 10.6MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

실패

리스트을 거의 안쓰는 방법으로... 

def solution(n, stations, w):
    gaps = []
    answer = last_end = 0
    for station in stations:
        start, end = station - w, station + w
        if start <= last_end:
            last_end = max(end, last_end)
        else:
            gaps.append(start - 1 - last_end)
            last_end = end
    if last_end < n:
        gaps.append(n - last_end)
    width = w * 2 + 1
    for gap in gaps:
        answer += gap // width + (1 if gap % width else 0)
    return answer

정확성  테스트
테스트 1 〉	통과 (0.06ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.8MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.03ms, 10.6MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.03ms, 10.7MB)
테스트 10 〉	통과 (0.04ms, 10.8MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.04ms, 10.7MB)
테스트 13 〉	통과 (0.04ms, 10.8MB)
테스트 14 〉	통과 (0.04ms, 10.7MB)
테스트 15 〉	통과 (0.03ms, 10.7MB)
테스트 16 〉	통과 (0.04ms, 10.7MB)
테스트 17 〉	통과 (0.04ms, 10.7MB)
테스트 18 〉	통과 (0.04ms, 10.7MB)
테스트 19 〉	통과 (0.04ms, 10.7MB)
테스트 20 〉	통과 (0.04ms, 10.7MB)
테스트 21 〉	통과 (0.04ms, 10.6MB)
효율성  테스트
테스트 1 〉	통과 (2.58ms, 15.1MB)
테스트 2 〉	통과 (2.82ms, 15.1MB)
테스트 3 〉	통과 (2.71ms, 15.1MB)
테스트 4 〉	통과 (2.71ms, 15MB)

성공

리스트를 안씀.

def solution(n, stations, w):
    answer = last_end = 0
    width = w * 2 + 1
    for station in stations:
        start, end = station - w, station + w
        if start <= last_end:
            last_end = max(end, last_end)
        else:
            gap = start - 1 - last_end
            answer += gap // width + (1 if gap % width else 0)
            last_end = end
    if last_end < n:
        gap = n - last_end
        answer += gap // width + (1 if gap % width else 0)
    return answer

정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.6MB)
테스트 2 〉	통과 (0.03ms, 10.5MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.05ms, 10.8MB)
테스트 7 〉	통과 (0.04ms, 10.6MB)
테스트 8 〉	통과 (0.04ms, 10.6MB)
테스트 9 〉	통과 (0.04ms, 10.8MB)
테스트 10 〉	통과 (0.04ms, 10.6MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.03ms, 10.8MB)
테스트 13 〉	통과 (0.04ms, 10.7MB)
테스트 14 〉	통과 (0.04ms, 10.8MB)
테스트 15 〉	통과 (0.03ms, 10.7MB)
테스트 16 〉	통과 (0.04ms, 10.6MB)
테스트 17 〉	통과 (0.04ms, 10.6MB)
테스트 18 〉	통과 (0.04ms, 10.7MB)
테스트 19 〉	통과 (0.04ms, 10.5MB)
테스트 20 〉	통과 (0.04ms, 10.7MB)
테스트 21 〉	통과 (0.04ms, 10.7MB)
효율성  테스트
테스트 1 〉	통과 (2.33ms, 15MB)
테스트 2 〉	통과 (2.44ms, 15.1MB)
테스트 3 〉	통과 (2.44ms, 14.9MB)
테스트 4 〉	통과 (2.40ms, 15MB)