[C++로 풀이] 기지국 설치⭐⭐⭐

📌 기지국 설치

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

🔥 1 차 풀이 ❌

#include <vector>
using namespace std;

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

    // already 에 추가 증설 전에도 전파를 전달 받을 수 있는 아파트 체크
    vector<bool> already(n + 1);
    int index = 0;
    for(int i = 1; i <= n; ++i){
        if (i >= stations[index] - w && i <= stations[index] + w)
            already[i] = true;
        if (i == stations[index] + w)
            index++;
        
        if (index == stations.size())
            break;
    }
    
    int count = 0;
    for(int i = 1; i <= n; ++i){
        // 전파를 전달받지 못한 아파트 카운팅
        if (already[i] == false)
            count++;
        
        // 전파를 전달 못받았는데 다음 아파트는 전파를 전달 받은(already[i + 1]) 상태라면 
        // 현재까지 전파를 전달받지 못한 아파트 범위를 카운팅 완료한 것
        if (already[i] == false && i + 1 <= n && already[i + 1] == true){
            answer += count / (2 * w + 1); // 2 * w + 1 으로 나눈 몫 만큼 (w=2 라면 기지국 하나로 2*2+1 = 5 개 아파트 전파 전달)
            if (count % (2 * w + 1) != 0) answer += 1; // 나머지에도 기지국 하나 세워주기
            count = 0; // 리셋
        }
    }
    
    // 전파가 전달되지 않는 마지막 아파트 범위는 위 for문에서 고려되지 못했기 때문에 한번 더
    if (count != 0){
        answer += count / (2 * w + 1);
        if (count % (2 * w + 1) != 0) answer += 1;
    }

    return answer;
}

시간 초과 두둥.. N 크기가 무려 200,000,000 2억이기 때문에 O(N) 연산만으로도 시간초과가 난다. 200,000,000 숫자만 보고 O(N)으로 풀어야지~ 라고 생각했었는데 안된다.. 200,000,000 크기를 보고는 O(N) 조차도 안되겠구나 라고 생각을 했었어야 했다!!!

N개의 아파트를 전부 순회하는 것은 시간초과가 발생하니 안된다.

🔥 2 차 풀이 ⭕

#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int count = 0; // 해당 범위에서의 아파트 개수
    
    // 가장 왼쪽의 "전파를 전달받지 못한 아파트 범위"
    count = stations[0] - w - 1 > 0 ? stations[0] - w - 1 : 0; 
    answer += count / (2 * w + 1);
    answer += count % (2 * w + 1) != 0 ? 1 : 0;
    // 그외 "전파를 전달받지 못한 아파트 범위"
    for(int i = 1; i < stations.size(); ++i){
        count = stations[i] - stations[i - 1] - 2 * w - 1 > 0 ? stations[i] - stations[i - 1] - 2 * w - 1 : 0;
        answer += count / (2 * w + 1);
        answer += count % (2 * w + 1) != 0 ? 1 : 0;
    }
    // 가장 오른쪽의 "전파를 전달받지 못한 아파트 범위"
    count = n + 1 - stations.back() - w - 1 > 0 ? n + 1 - stations.back() - w - 1 : 0;
    answer += count / (2 * w + 1);
    answer += count % (2 * w + 1) != 0 ? 1 : 0;

    return answer;
}

굳이 아파트 N개를 순회하지 않아도, stations의 원소(기지국)들 간의 간격을 통해 “전파를 전달받지 못한 아파트 범위”를 구할 수 있다. 이것만 구하면 필요한 최소 증설 개수도 구할 수 있고! 즉, stations만 순회하면 되는데 stations 크기는 최대 10,000 이기 때문에 시간초과가 발생하지 않는다.

• 1️⃣ 가장 왼쪽의 “전파를 전달받지 못한 아파트 범위”
  • 예제 1 번의 경우 1,2번 아파트가 이에 해당한다.
    • 4(stations[0]) - 1(stations[0] 본인) - 1(w) = 2 이렇게 2 개!
  • 예제 2 번의 경우 1,2,3,4,5,6번 아파트가 이에 해당한다.
    • 9(stations[0]) - 1(stations[0] 본인) - 2(w) = 6 이렇게 6 개!
• 2️⃣ 그외 가운데의 “전파를 전달받지 못한 아파트 범위”
  • 👉 이전 기지국 위치를 뺀 것에서 구한다.
  • 예제 1 번의 경우 6,7,8,9 번 아파트가 이에 해당한다.
    • 11(stations[1]) - 4(stations[0] 이전기지국) - 1(stations[1] 본인) - 2 * 1(w 중간 범위는 양쪽에서 w 가 2개) = 4 이렇게 4 개!
  • 예제 2 번의 경우엔 이 for문을 돌지 않는다. stations.size()가 1 이여서
• 3️⃣ 가장 오른쪽의 “전파를 전달받지 못한 아파트 범위”
  • 👉 16개의 아파트가 있다면 가상의 17번 아파트에서 마지막 기지국 위치를 뺀 것에서 구함
    • 예제 1 번의 경우 n + 1 - stations.back() - w - 1 가 음수가 되기 때문에 0 으로 처리. 즉 예제 1 번은 오른쪽 범위가 없는 것으로 처리 함
    • 예제 2 번의 경우 12,13,14,15,16 번 아파트가 이에 해당한다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기