[프로그래머스] lv3. 기지국 설치 / Python, JavaScript

프로그래머스

Lv3. 기지국 설치

접근한 방법

각 자리의 기지국 설치 여부를 배열로 다루게 되면 효율성 테스트에서 탈락됩니다. 굳이 설치여부를 다룰 필요 없이 해당 범위만 건너뛰면서 탐색했습니다.

 

주어진 stations를 먼저 고려하기 위해 이 어레이를 큐나 스택으로 활용합니다. 오름차순으로 되어있는 김에 큐로 사용하는 것이 낫고 자바스크립트에서는 front 포인터를 두어서 큐 처럼 활용합니다. 현재 위치에 기지국을 설치할지 말지를 결정하는데 그 위치가 미리 설치된 기지국(A)의 범위 안에 들면 탐색할 필요 없이 A의 범위 끝으로 이동하면 되고 A를 큐에서 제거해줍니다.

 

주어진 stations를 모두 설치(확인)했다면 이제 남아있는 공간에 대해서 설치를 해주면 됩니다. 

주어진 예시를 예로 들면 가장 먼저 1번부터 확인합니다. 큐에는 [4, 11]이 들어있습니다. 현재 위치(1)이 큐의 front인 4의 최대 전달 범위(3~5)에 들지 않기 때문에 1은 설치해야 하는 위치입니다. 설치 후 다음 위치는 현재 위치 + w * 2 + 1로 해줍니다. 1에 설치할 경우 3까지는 확인하지 않아도 되는데 왜냐하면 어차피 4에서 설치될 것이고 3의 위치가 커버되기 때문입니다. (예를 들어 w가 3이라면 1에 설치할 경우 8부터 확인하면 됩니다. 왜냐하면 8에서 설치하기 때문에 5까지의 위치가 커버되기 때문입니다)

 

다음 확인 위치는 4입니다. 4는 현재 큐의 front인 4의 최대 전달 범위(3~5)에 들기 때문에 위치를 4+w+1로 이동해주고 큐에서 제거해줍니다.

다음 확인 위치는 6입니다. 이때는 현재 큐의 front인 11의 최대 전달 범위(10~11)에 들지 않기 때문에 6에 설치해주고 6 + w * 2 + 1인 9로 이동합니다.

다음 확인 위치는 9입니다. 9는 현재 큐의 front인 11의 최대 전달 범위에 들지 않기 때문에 9에 설치해주고 9 + w * 2 + 1인 12로 이동합니다.

다음 확인 위치는 12인데 범위를 넘어가므로 종료합니다.

 

 

Python

def solution(n, stations, w):
    from collections import deque
    q = deque(stations)
    now, result = 1, 0
    while 1:
        if now > n:
            break
        if q: # 아직 확인하지 않은 설치된 기지국(stations)이 남아 있는 경우
        	# 현재 위치가 설치된 기지국의 범위 안에 드는 경우
            if now >= q[0] - w and now <= q[0] + w: 
                now = q.popleft() + w + 1 # 탐색 위치를 해당 기지국 범위 위치 끝(오른쪽)으로 이동
                continue
        else:
        	# 현재 설치할 위치의 최대 전달 범위가 n을 초과하면 종료
            if now + w > n:
                result += 1
                break
        # 현재 위치에 기지국을 설치했을 때 최대 전달 범위 위치 끝(오른쪽)으로 이동
		now += w * 2 + 1 
        result += 1
    return result

JavaScript

function solution(n, stations, w) {
    let s = 0;
    let [now, result] = [1, 0];
    while (1) {
        if (now > n) break;
        if (s < stations.length) {
            const front = stations[s];
            if (now >= front - w && now <= front + w) {
                now = stations[s++] + w + 1;
                continue;
            }
        } else {
            if (now + w > n) {
                result += 1;
                break;
            }
        }
        now += w * 2 + 1;
        result += 1;
    }
    return result;
}