Summer/Winter Coding(~2018)기지국 설치 - c++

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

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

해당 문제는 존재하는 기지국을 5G로 바꾸면서 생기게 되는 전파의 공백을 채우는 문제이다.

가장 먼저 생각했던 문제는 5G로 바꾸면 범위가 닿지 않는 곳을 false 만약 범위 안에 존재하는 곳 이라면 true로 바꾸고, false들의 범위들을 계산하여 answer를 도출했다. 하지만 이 방법은 시간 초과가 발생했다.

 

다음은 시간 초과가 발생했던 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> stations, int w){
    int answer = 0;
    vector<int> visit;
    for(int i=0;i<=n;i++){
        visit.push_back(false);
    }
    
    for(int i=0;i<stations.size();i++){
        int station = stations[i];
        int start = station-w>=0?station-w:0;
        int end = station+w>n?n:station+w;
    
        for(int j = start;j<=end;j++){
            visit[j] = true;
        }
    }
    
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(i==n&&visit[i]==false){
            cnt++;
            if(cnt%(w*2+1)>0) answer++;
            answer+=cnt/(w*2+1);
            break;
        }
        
        if(visit[i]==false){
            cnt++;
        }else if(visit[i]==true){
            if(cnt%(w*2+1)>0) answer++;
            answer+=cnt/(w*2+1);
            cnt=0;
            continue;
        }
    }

	return answer;
}

 

 이때 answer에 w*2+1을 나눈것을 더하는 이유는 w*2는 기준점의 좌우를 커버하는 범위 이고 +1이 기준점을 의미하기 때문에 해당 범위을 커버할수 있는 기지국의 수를 구할수 있다. 또한 나머지가 발생할 경우 커버하지 못하는 범위가 있다는 의미이기 때문에 answer에 1을 더해주어야 하는 것이다.

 

 방법을 생각 하다 보니 애초에 범위가 아니기 시작한곳에서 기지국의 범위 직전까지의 거리를 구한뒤 위에서 사용했던 식을 동일하게 쓰게 되면 이중 for문을 쓸필요가 없었단걸 알게 됐다. (기지국 범위 체크 자체가 불 필요 했던 것이다...)

 

고친 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> stations, int w){
    int answer = 0;
    int start;
    int end;
    int where=0;

	for(int i=0;i<stations.size();i++){
    	start = stations[i]-w-1;
        end = stations[i]+w-1;
        
        answer+=(start-where)/(w*2+1);
        if((start-where)%(w*2+1)>=1) answer++;
        where = end+1;
    }
    
    if(where<n){
    	answer+=(n-where)/(w*2+1);
        if((n-where)%(w*2+1)>=1) answer++;
    }

	return answer;
}

훨씬 간결하게 코드가 완성이 되는것을 알수가 있다.

 

여기서 마지막 if문의 경우 station이 중간 부분에만 있어 마지막까지 계산해야 되는 것을 하지 못할때를 계산하기 위한 부분입니다.!