[프로그래머스] 기지국 설치

기지국 설치(https://programmers.co.kr/learn/courses/30/lessons/12979)

---

1. 이해하기

• 기존에 기지국이 설치되어 있는 곳도 있고 없는 곳도 있다.
• 기지국이 설치되어 있는 곳은 w만큼의 지역을 커버한다.
• 최소의 기지국을 설치하고 모든 아파트에 전파를 전달하려고 한다.

---

2. 구현하기

• 기지국이 설치되어 있지 않은 지역의 시작을 start, 기지국이 설치되어있는 곳의 위치를 location이라고 한다면 기지국이 설치되고 전파가 전달되는 곳 중 왼쪽 l은 location-w-1이다.

  • 이 때, 전파가 전달되지 않는 지역의 거리 len은 l-start+1이다. 이를 이용하면 이 구간에 몇개의 기지국을 설치해야하는지 알 수 있다.

  • len/(w*2+1)을 통해 기지국이 몇개가 들어갈 수 있는지 알 수 있고 len%(w*2+1)으로 한개를 더 설치해야 하는지 여부를 알 수 있다.

  • Python

    def solution(n, stations, w):
        answer = 0
        start = 1
        done = False
        for location in stations:
            l = location-w-1
            length = l-start+1
            if length < 0: length = 0
            answer += length//(w*2+1)
            answer += 1 if length%(w*2+1) else 0
            r = location+w+1
            if r > n:
                done = True
                break
            start = r
        if not done:
            length = n-start+1
            answer += length//(w*2+1)
            answer += 1 if length%(w*2+1) else 0
        return answer

  • C++

    #include <iostream>
    #include <vector>
    using namespace std;
    
    int solution(int n, vector<int> stations, int w)
    {
        int answer = 0;
    
        int start = 1;
        bool done = false;
        for(int i = 0; i < stations.size(); i++) {
            int l = stations[i]-w-1;
            int len = l-start+1;
            if(len < 0) len = 0;
            answer += len/(w*2+1);
            answer += (len%(w*2+1) == 0)?0:1;
            int r = stations[i]+w+1;
            if(r > n) {
                done = true;
                break;
            }
            start = r;
        }
        if(!done) {
            int len = n-start+1;
            answer += len/(w*2+1);
            answer += (len%(w*2+1) == 0)?0:1;
        }
        return answer;
    }