[프로그래머스 C++] 기지국 설치

 

[프로그래머스 C++] 기지국 설치

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

 

해결전략

 

 

 

---

 

 

처음 시도한 코드

 

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
 
int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
 
    int x = 0;
    int block = w + 1 + w; // w + 1 + w를 하나의 블록으로 취급
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cnt++;
 
        if (x < stations.size() && i == (stations[x] - 1)) { // 기지국이 설치된 아파트
            cnt -= (w + 1);
            if (cnt > 0) {
                if (cnt % block == 0) answer += (cnt / block);
                else answer += (cnt / block + 1);
            }
 
            cnt = 0;
            i += w;
            x++;
 
        }
        else if (i == n - 1) { // 마지막 아파트
            if (stations[x-1] - 1 + w > i) continue;
            if (cnt > 0) {
                if (cnt % block == 0) answer += (cnt / block);
                else answer += (cnt / block + 1);
            }
        }
        
    }
 
    return answer;
}
 
int main(){
    cout << solution(13, { 3, 7, 11 }, 1) << "\n"; // 4
    cout << solution(5, { 3 }, 2) << "\n"; // 0
    cout << solution(6, { 3 }, 2) << "\n"; // 1
    cout << solution(6, { 4 }, 2) << "\n"; // 1
    cout << solution(16, { 1, 16 }, 2) << "\n"; // 2
    cout << solution(11, { 1, 4 }, 1) << "\n"; // 2
    cout << solution(11, { 1, 5 }, 1) << "\n"; // 3
    cout << solution(5, { 1, 2, 3, 4, 5 }, 1) << "\n"; // 0
    cout << solution(200000000, { 100000000 }, 5) << "\n"; // 18181818
 
    return 0;
}

 

---

 

정답코드

 

#include <iostream>
#include <vector>
using namespace std;
 
int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
 
    int x = 0;
    int block = w + 1 + w;
    int cnt = 0;
    int position = 1;
 
    for (int i = 0; i < stations.size(); i++) 
    {
        // 기지국이 설치된 범위의 시작과 끝
        int start = max(1, stations[i] - w);
        int end = min(n, stations[i] + w);
 
        // 기지국이 설치된 범위 이전의 빈 공간 계산
        if (position < start) {
            cnt = start - position;
            if (cnt > 0) {
                if (cnt % block == 0) answer += (cnt / block);
                else answer += (cnt / block + 1);
            }
        }
 
        // 다음 조사 시작 지점을 기지국 설치 범위 이후로 설정
        position = end + 1;
    }
 
    // 마지막 기지국 이후의 빈 공간 계산
    if (position <= n) {
        cnt = n - position + 1;
        if (cnt > 0) {
            if (cnt % block == 0) answer += (cnt / block);
            else answer += (cnt / block + 1);
        }
    }
 
    return answer;
}

 

---