[프로그래머스] Summer/Winder Coding 기지국 설치 level3

문제 :

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

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

 

분석 :

 

시간초과 + 에러난 c++ 코드 :

//
//  [SW] 2018_BaseStation.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/05/06.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <math.h>

using namespace std;

//vector<int> stations = {4, 11};
vector<int> stations = {9};
int w = 2;
int n = 16;


int main(){
    int arr[n+1];
    memset(arr, 0, sizeof(arr));


    for(int i = 0; i < stations.size(); i++){
        int start = stations.at(i) - w;
        int end = stations.at(i) + w;
        while(start <= end){
            arr[start] = 1;
            start++;
        }
    }
    
    
    vector<pair<int, int>> segment;

    int s = 0, d = 0;
    int j = 1;
    while(j <n){
        if(arr[j] == 0){
            if(s == 0){
                s = j;
            }else{
                d = j;
            }
        }else{
            if(s != 0){
                d = j;
                segment.push_back({s, d});
                s = 0; d = 0;
            }
        }
        j++;
    }
    //0으로 끝났을 때
    if(s != 0){
        d = j;
        segment.push_back({s, d});
    }

    int antenaCount = 0;


    for(int i =0; i <segment.size(); i++){
        float segLength = (float)segment.at(i).second - (float)segment.at(i).first;
        antenaCount += ceil(segLength / (1+ 2*w));
    }
    cout << antenaCount << '\n';
    
    return 0;
}

 

기지국을 배열을 만들어 기지국이 설치된 곳에는 1을 넣어 0인 구간을 segment 벡터에 pair 식으로 담아 그 구간의 길이에 대해 설치할 수 있는 안테나를 구해 더하는 식으로 작성했다.

테스트 케이스에 대해 2개가 통과가 안됐고 (1번, 15번) 그리고 효율성 제로였다 하하 😐😐

 

그래서 질문 풀이를 보고 배열 없이 푸는 방법도 있다 하여 다른 블로그 글을 참고하여 풀었다.

이런 방법이 있다니 ..! 신기하다 

 

//
//  [SW] 2018_BaseStation.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/05/06.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <math.h>

using namespace std;

//vector<int> stations = {4, 11};
vector<int> stations = {9};
int w = 2;
int n = 16;


int main(){
    int begin = 0; int answer = 0;
           
       for(int i = 0; i < stations.size(); i++){
           int start = stations.at(i) - w - 1;
           int nextStart = stations.at(i) + w - 1;
           if(begin >= start && begin <= nextStart){
               //station 겹치는 부분
               begin = nextStart + 1;
               continue;
           }
           answer += ceil((float)(start - begin)/ (float)(1 + 2*w));
           begin = nextStart + 1;
       }
       
       if(begin < n){
           answer += ceil((float)(n - begin)/ (float)(1 + 2*w));
       }
       cout <<answer << '\n';
    return 0;
}

 

코드도 훨씬 짧고 직관적인거 같다 .. 👍