lv3 ) 기지국 설치 [다시]

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

 

두번째 풀이(답)

1중 for로, visited 없이 진행

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

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

    for(int y = 1 ; y <=n;y){
        if(!stations.empty()){
           int tar = stations.back();
           if(tar == y || (tar - w <= y &&tar +w >= y  )){
               y = tar + w + 1;
               stations.pop_back();
            }
            else{
                answer++;
                 y = y + (w*2) + 1;
          }
        }
        else{
            answer++;
            y = y + (w*2) + 1;
        }
    }


    return answer;
}

 

풀이법:

vector를 잘 활용. vector를 내림차순으로 진행해야 가까운 기지국 pop 활용 가능

y + (w*2) + 1 은 기지국 전파 영역이다.

만일 현재 인덱스가 전파국 범위(station - w, station + w)에 있다면 현재 인덱스 위치를 station + w + 1로 갱신 후 다음 전파국 여부를 체크한다.

전파국 범위에 현재 위치가 있지 않으면 전파국을 설치(answer ++) 후 (전파 영역) + 1 위치로 y를 갱신한다. 

---

 

첫번째 풀이(오답)

2억 공간배치 및 2중 for에 따라 효율성에서 dump cored 발생

[내 코드]

효율성에서 틀림

#include <iostream>
#include <vector>
using namespace std;
int visited[200'000'000];
int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    //1. 초기화 N의 영역(visited 영역)에서 stations의 값 에 W범위를 0에서 1로 초기화

    //2.  (w*2) + 1 이 visit 0을 만났을때 해당 w*2 + 1영역까지 visit 1로 만들어야함.
    //3. 2포함 0만날때마다 answer ++ 추가
    //그리디 느낌
    for(int y = 0; y < stations.size(); ++y){
        int tar = stations[y];
        for(int x = tar - w - 1; x<tar+w; ++x){
            if(x < 0)continue;
            visited[x] = 1;
        }
    }
    for(int y = 0 ; y <n;++y){
        if(visited[y] == 0){
            answer++;
            for(int x = y; x < y + (w*2) + 1;++x){
                visited[x] = 1;
            }
        }
        
    }


    return answer;
}

 

 

틀린이유(LLM 설명)

핵심 문제: 메모리 + 시간 초과

 

1. 가장 큰 문제 — 배열 크기

 

int visited[200'000'000]; // 200MB 스택 할당 → 즉시 런타임 에러

• int 1개 = 4bytes → 200,000,000 × 4 = 800MB
• 스택 메모리 한계 보통 1~8MB → 스택 오버플로우

 

2. 시간 복잡도 문제

현재 코드 최악의 경우

stations 초기화: 10,000 × 20,000 = 200,000,000
메인 루프:       200,000,000 × 20,001 = 사실상 무한

O(N × W) 수준이라 N=2억, W=1만이면 절대 통과 불가하다.

 

가지치기로 해결이 안된다.

근본적인 이유

N = 2억, W = 1만
visited 배열 자체가 800MB → 선언하는 순간 끝

가지치기는 탐색 경우의 수를 줄이는 건데, 이 문제는 탐색 전에 메모리 할당 자체가 불가능한 구조이다.

쉽게 말하면

"2억 칸짜리 노트를 펼치려는데 노트 자체가 책상에 안 올라감"

 

가지치기는 노트에 뭘 쓸지 줄이는 거지, 노트 크기를 줄이는 게 아니다.

---

이런 구간 유형 문제 만나면 드는 신호

• N이 1억 이상이면 배열로 접근하면 안 됨
• 구간, 범위 얘기가 나오면 수학적으로 계산하는 방향 먼저 생각하기