Programmers_Level3_기지국 설치

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

프로그래머스

 

---

 

 

문제 접근 방식은 설치된 기지국의 전파 범위를 담은 백터를 이용하여 

기지국을 설치해 가는 방식이었는데 

정확도에서는 맞았지만 효율성에서 다 틀렸다... 

 

아마 백터를 새로 하나 만들어서 그런듯하다. 

그래서 새로는 백터를 만들지 않고 기지국을 설치하는 방법으로 접근을 해보았다.

 

오답 코드 (70.5점) 

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


class StationInstaller
{
    private: 
    vector<int> apt; 
    int n = 0;
    int w = 0;
    int answer = 0;
    
    public: 
    StationInstaller(int n, vector<int>& stations, int w){
        this->apt.resize(n + 1);
        this->n = n;
        this->w = w;
        
        stationRange(stations, w);
    };
    void stationRange(vector<int>& stations, int w);
    void installStations();
    int getAnswer(){ return answer; };
};

// 기지국의 전파 범위 확인
void StationInstaller::stationRange(vector<int>& stations, int w)
{
    for(int station : stations)
    {
        int temp = station - w; 
        int start = temp < 0 ? 0 : temp;
        
        temp = station + w; 
        int end = temp > n ? n : temp;       
        
        for(int idx = start ; idx <= end; ++idx)
        {
            apt[idx] = 1;
        }
    }
}

void StationInstaller::installStations()
{    
    for(int idx = 1; idx <= n; ++idx)
    {
        // 기지국의 전파 범위 내라면
        if(apt[idx] == 1)
        {
            continue;
        }
        // 전파 범위 밖이라면 기지국을 만들고 전파 범위 만큼 idx를 옮긴다
        else
        {
            answer++; 
            idx += w * 2;
        }      
    }
}

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

    StationInstaller myStation(n , stations, w);
    myStation.installStations();
    
    answer = myStation.getAnswer();
    
    return answer;
}

 

 

 

for문 자체가 아파트들이라고 생각하고 

stations의 전파 범위 안에 들어왔는지를 체크했다. 

 

 

정답 코드 (100점)

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

class StationInstaller
{
    private: 
    int answer = 0;
    
    public: 
    void installStations(int n, vector<int> stations, int w);
    int getAnswer(){ return answer; };
};

void StationInstaller::installStations(int n, vector<int> stations, int w)
{    
    // 기지국 설치된 위치 인덱스
    int i = 0;
    
    for(int idx = 1; idx <= n; ++idx)
    {
        // 기지국 전파 범위안에 있는지?  기지국 설치 위치 인덱스가 범위 안인지? 
        if(idx <= stations[i] + w && idx >= stations[i] - w && i < stations.size())
        {
            // 전파 최대 범위로 이동
            idx = stations[i] + w;
            i++;
        } 
        else
        {
            answer++;
            idx += w * 2;
        }      
    }
}

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    StationInstaller myStation;
    
    myStation.installStations(n, stations, w);
    answer = myStation.getAnswer();
    
    return answer;
}

 

 

 

오답 코드 (좌) / 정답 코드 (우)