[코테연습] 기지국 설치

https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=python3

프로그래머스

 

문제 타입

• 구간 커버링 문제: 일정 구간을 커버하기 위해 최소한의 자원을 배치해야 하는 문제.
• 그리디 알고리즘: 각 단계에서 최적의 선택을 반복적으로 수행하여 전체 최적화를 추구.
• 수학적 계산 문제: 특정 범위를 커버하는 수학적 계산을 포함.

---

문제 분석

• 목표:
  • 주어진 길이 N과 기지국의 커버 범위 W가 있을 때, 이미 설치된 기지국(stations)을 보완하여 모든 구간을 커버할 최소 기지국 개수를 계산.
• 제약:
  • 기지국은 양쪽 W만큼 커버 가능.
  • 추가 기지국을 최소화해야 함.
• 입력:
  1. N: 총 길이.
  2. stations: 기존 기지국 위치 배열.
  3. W: 기지국의 커버 범위.
• 출력:
  • 모든 구간을 커버하기 위한 최소 기지국 개수.
• 핵심 아이디어:
  • 기지국 간 비어 있는 구간과 마지막 기지국 이후의 남은 구간을 각각 계산하여 추가 기지국 개수를 구함.
  • 하나의 기지국이 커버할 수 있는 범위는 2 * W + 1.

---

문제 풀이

1. 필요한 변수 정의:
   • current: 현재 커버되지 않은 시작 위치 (초기값 1).
   • range: 하나의 기지국이 커버할 수 있는 범위 (2 * W + 1).
   • answer: 필요한 기지국 개수 누적.
2. 주어진 기지국을 기준으로 구간 처리:
   • 각 기지국의 커버 범위(start = station - W, end = station + W)를 계산.
   • 현재 커버되지 않은 시작 위치(current)와 기지국 커버 시작 위치(start)를 비교:
     • 커버되지 않은 구간이 있을 경우:
       • 커버되지 않은 구간 길이(uncovered = start - current)를 계산.
       • 커버하기 위한 추가 기지국 개수를 (uncovered + range - 1) / range로 계산하고 answer에 추가.
     • 커버 가능할 경우:
       • 아무 작업도 필요 없음.
   • current를 현재 기지국 커버 범위 끝 다음(end + 1)으로 갱신.
3. 마지막 구간 처리:
   • 모든 기지국이 처리된 이후, 남아 있는 커버되지 않은 구간을 확인 (current <= N).
   • 남아 있는 구간이 있을 경우:
     • 구간 길이(uncovered = N - current + 1)를 계산.
     • 커버하기 위한 추가 기지국 개수를 (uncovered + range - 1) / range로 계산하고 answer에 추가.
4. 결과 반환:
   • answer에 최종 추가 기지국 개수를 반환.

 

 

> java

 

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int current = 1; // 현재 커버되지 않은 시작 위치
        int range = 2 * w + 1; // 기지국 하나가 커버할 수 있는 범위

        for (int station : stations) {
            int start = station - w;
            int end = station + w;

            // 현재 기지국으로 커버할 수 없는 영역 처리
            if (current < start) {
                int uncovered = start - current; // 커버되지 않은 길이
                answer += (uncovered + range - 1) / range; // 필요한 기지국 개수
            }
            current = end + 1; // 다음 커버되지 않은 시작 위치
        }

        // 마지막 기지국 이후로 남아 있는 구간 처리
        if (current <= n) {
            int uncovered = n - current + 1;
            answer += (uncovered + range - 1) / range;
        }

        return answer;
    }
}

 

 

> python

 

def solution(n, stations, w):
    answer = 0
    current = 1
    _range = w * 2 + 1
    
    for stat in stations : 
        start = stat - w
        end = stat + w
        
        if current < start :
            uncovered = start - current
            answer += int((uncovered + _range - 1) / _range)
        current = end + 1
        
    if current <= n :
        uncovered = n - current + 1
        answer += int((uncovered + _range - 1) / _range)
        
    return answer

 

 

 

코드 분석

 

if (current < start) {
    int uncovered = start - current; // 커버되지 않은 길이 계산
    answer += (uncovered + range - 1) / range; // 필요한 기지국 개수 계산
}

 

1. current < start 확인

• **현재 커버되지 않은 시작 위치 (current)**가 **기지국이 커버할 수 있는 범위의 시작점 (start)**보다 작을 때 실행됩니다.
• 이 조건은 "기지국 이전에 커버되지 않은 구간이 존재한다"는 뜻입니다.

2. 커버되지 않은 길이 계산

int uncovered = start - current;

 

 

• uncovered는 커버되지 않은 구간의 길이입니다.
• start - current는 커버되지 않은 구간의 시작부터 끝까지의 길이를 계산합니다.

3. 필요한 기지국 개수 계산

answer += (uncovered + range - 1) / range;

 

 

• (uncovered + range - 1) / range는 커버되지 않은 구간을 모두 커버하기 위해 필요한 기지국의 개수를 계산합니다.
• 계산 원리:
  • range는 하나의 기지국이 커버할 수 있는 범위의 길이입니다.
  • (uncovered + range - 1) / range는 "uncovered 길이를 range로 나누어 올림"의 역할을 합니다.
    • + range - 1: 나머지가 있을 경우 올림 효과를 주기 위해 추가된 부분입니다.
    • 예) uncovered = 4, range = 3인 경우:
      • (4 + 3 - 1) / 3 = 6 / 3 = 2 (기지국 2개 필요)

예시를 통한 이해

예시 1: current = 1, start = 4, w = 1

• 주어진 값:
  • range = 2 * w + 1 = 3
  • uncovered = start - current = 4 - 1 = 3
• 계산:
•  

answer += (uncovered + range - 1) / range;
answer += (3 + 3 - 1) / 3;
answer += 5 / 3;
answer += 1; // 기지국 1개 필요

 

 

 

예시 2: current = 1, start = 7, w = 2

• 주어진 값:
  • range = 2 * w + 1 = 5
  • uncovered = start - current = 7 - 1 = 6
• 계산:

answer += (uncovered + range - 1) / range;
answer += (6 + 5 - 1) / 5;
answer += 10 / 5;
answer += 2; // 기지국 2개 필요

 

예시 3: current = 6, start = 10, w = 1

• 주어진 값:
  • range = 2 * w + 1 = 3
  • uncovered = start - current = 10 - 6 = 4
• 계산:
•  

answer += (uncovered + range - 1) / range;
answer += (4 + 3 - 1) / 3;
answer += 6 / 3;
answer += 2; // 기지국 2개 필요

 

최종 정리

1. if (current < start): 커버되지 않은 구간이 있을 경우, 해당 구간의 길이를 계산.
2. uncovered: 커버되지 않은 길이.
3. (uncovered + range - 1) / range: 필요 기지국 개수를 올림하여 계산.
4. answer += ...: 기지국 개수를 누적.

 

 

코드 분석

 

if (current <= n) {
    int uncovered = n - current + 1;
    answer += (uncovered + range - 1) / range;
}

 

주요 변수

1. current: 현재 커버되지 않은 시작 위치.
2. n: 총 길이 (구간의 끝 위치).
3. uncovered: n - current + 1로 계산되며, 남아 있는 커버되지 않은 구간의 길이를 나타냄.
4. range: 하나의 기지국이 커버할 수 있는 범위의 길이 (2 * w + 1).
5. answer: 필요한 기지국 개수를 누적.

코드의 동작

1. if (current <= n):
   • 현재 커버되지 않은 위치(current)가 전체 길이(n) 이하라면, 남아 있는 커버되지 않은 구간이 있다는 뜻입니다.
   • 예를 들어:
     • current = 12, n = 16일 경우, 남아 있는 구간은 [12, 16]입니다.
2. 남아 있는 구간 길이 계산:

int uncovered = n - current + 1;

 

 

• n - current + 1은 마지막 구간의 길이를 계산합니다.
• 예를 들어:
  • current = 12, n = 16인 경우, uncovered = 16 - 12 + 1 = 5.

필요한 기지국 개수 계산:

 

answer += (uncovered + range - 1) / range;

 

 

 

• • (uncovered + range - 1) / range는 커버되지 않은 길이를 하나의 기지국 범위(range)로 나누어 올림한 값을 계산합니다.
  • 계산 방식은 이전 로직과 동일하며, **올림 효과를 주기 위해 + range - 1**을 더합니다.
• 결과 누적:
  • 계산된 기지국 개수를 answer에 누적합니다.

예시를 통한 이해

예시 1: n = 16, current = 12, w = 2

• 주어진 값:
  • range = 2 * w + 1 = 5
  • uncovered = n - current + 1 = 16 - 12 + 1 = 5
• 계산:

answer += (uncovered + range - 1) / range;
answer += (5 + 5 - 1) / 5;
answer += 9 / 5;
answer += 1; // 기지국 1개 필요

 

 

 

예시 2: n = 20, current = 15, w = 1

• 주어진 값:
  • range = 2 * w + 1 = 3
  • uncovered = n - current + 1 = 20 - 15 + 1 = 6
• 계산:

answer += (uncovered + range - 1) / range;
answer += (6 + 3 - 1) / 3;
answer += 8 / 3;
answer += 2; // 기지국 2개 필요

 

예시 3: n = 10, current = 11, w = 1

• 주어진 값:
  • current = 11이고 n = 10이므로 current > n.
  • 결과:
    • if (current <= n) 조건이 거짓이므로 이 로직은 실행되지 않습니다.
  •