[프로그래머스] 기지국 설치 - 파이썬(Python3)

프로그래머스 level 3 기지국 설치

->programmers.co.kr/learn/courses/30/lessons/12979

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

이번 문제는 기지국 설치 문제입니다!

꽤 생각을 요하지만, 굉장히 단순한 아이디어로 풀 수 있습니다.

 

같이 풀어볼게요!

---

풀이 아이디어

 

그리고 집의 개수가 N일때

선형복잡도 O(N)을 가지면 효율성 테스트를 통과하지 못하고,

station의 개수가 T라면 O(T)로 문제를 풀어내야 합니다.

 

즉, 집 리스트를 돌면서 전기가 있나 없나 확인하는 방법으로는

이 문제를 풀지 못합니다.

 

실제로 2억개나 되는 원소들을 담을 리스트는 꽤 묵직해서

만들기 어렵습니다.

 

대신에 station의 개수가 10000개 이하이므로

station과 연관지어서 풀이할 방법을 찾으면 될 것 같습니다.

 

그리고 봤더니, station 하나를 기준으로 양쪽으로

전기가 들어오지 않는 집들을 묶을 수 있습니다.

 

그러므로 station이 T개라면 전기가 들어오지 않는 집들을

최대 T+1개의 묶음으로 묶을 수 있습니다.

 

그리고 각 묶음들 안에서 설치해줘야 하는 station의 개수를

모두 합치면 됩니다.

 

바로 구현해보겠습니다.

---

구현

먼저 위에서 말씀드린 과정을 예시로 설명해보겠습니다.

 

집이 1번부터 15번까지 있고, station은 4, 13에 w는 1이라고 생각하면

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15

x  x  o  o  o  x  x   x  x   x    x    o   o    o   x

과 같이 됩니다.

그럼 여기서 전기가 들어오지 않는 집들끼리 모아놓은 묶음은

[1, 2], [6, 7, 8, 9, 10, 11], [15] 처럼 됩니다.

 

하지만 묶음의 모든 집을 표시하면, 2억개에 가까운 개수를 다 표시해야 할 수도 있으므로

처음 집과 끝 집만 나타내주도록 합니다.

 

그럼 다시 [1, 2], [6, 11], [15, 15] 와 같이 되겠네요.

 

이제 각 묶음들에 대해서 station을 설치해 줍시다.

[1, 2] 묶음에는 1개, [6, 11] 묶음에는 2개, [15, 15] 묶음에는 1개 해서

답은 4개가 됩니다.

 

여기서 묶음을 왜 따로 생각해도 되냐면

n번 묶음의 양 끝에 station을 설치해도 n-1번 묶음과 n+1번 묶음에는

영향을 미칠 수 없기 때문입니다.

 

생각보다 간단한 아이디어로 풀립니다.

 

구현한 코드와 채점 결과입니다.

def solution(n, stations, w):
    my_houses = []
    s = 1
    e = 0
    for station in stations:
        e = station-w-1
        if s > e:
            pass
        else:
            my_houses.append([s, e])
        
        s = station+w+1
        
    if s > n:
        pass
    else:
        my_houses.append([s, n])
    
    count = 0
    for e in my_houses:
        a = (e[1] - e[0] + 1) // ((2*w)+1)
        b = (e[1] - e[0] + 1) % ((2*w)+1)
        count += a
        if b == 0:
            pass
        else:
            count += 1
            
    return count