프로그래머스) Lv.3 - 기지국 설치

코딩테스트 연습 - 기지국 설치 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

문제는 생각보다 간단했지만 특정 조건에서 조금 애먹었던 문제

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

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int between;
    
    for(int i = 0; i < stations.size()-1; i++) {
        if(stations[i] + w < stations[i+1] - w) {
            between = (stations[i+1] - w) - (stations[i] + w) - 1;
            if(between % (2*w + 1) != 0) {
                answer += between / (2*w + 1) + 1;
            }
            else {
                answer += between / (2*w + 1);
            }
        }
    }
    
    if(stations[0] - w > 1) {
        between = (stations[0] - w) - 1;
        if(between % (2*w + 1) != 0) {
            answer += between / (2*w + 1) + 1;
        }
        else {
            answer += between / (2*w + 1);
        }
    }
    
    if(stations[stations.size()-1] + w < n) {
        between = n - (stations[stations.size()-1] + w);
        if(between % (2*w + 1) != 0) {
            answer += between / (2*w + 1) + 1;
        }
        else {
            answer += between / (2*w + 1);
        }
    }
    
    return answer;
}

처음 생각은 기지국이 닿는 곳을 배열로 저장하려고 했지만 시간이 오래걸릴 듯 하여 방법을 바꿨다.

 

이전 기지국이 닿는 높은 station 값과 그 다음 기지국이 닿는 낮은 station 값을 이용하여 그 사이의 거리를 구했다.

이 사이의 거리를 단순히 기지국이 닿는 범위로 나누어줬는데 이때 [몫+1]은 기지국이 설치되는 갯수다.

단, 나눌 때 나머지가 0인 경우 (나누어떨어지는 경우) 몫 자체가 갯수가 된다.

 

특정 조건은 가장 앞의 기지국과 가장 뒤의 기지국에 해당하는 경우이다.

 

1번의 station부터 가장 앞 기지국이 닿는 낮은 station 값 사이와 가장 마지막 기지국이 닿는 높은 station 값 부터 마지막 station 값 사이에도 기지국이 얼마나 설치되는지 계산을 따로 해줘야한다.

 

헷갈렸던 점은 예를 들어 가장 앞 기지국과 그 다음 기지국이 닿는 낮은 station 값이 1보다 작을 때 어떻게 해주어야하는가 였다. 헷갈린 이유는 알고리즘을 처음 짤 때 if문 안에 다음과 같은 조건이 더 있었기 때문이었다.

for(int i = 0; i < stations.size()-1; i++) {
        if(stations[i] - w > 1 && stations[i] + w < n &&
        	stations[i] + w < stations[i+1] - w) {
            between = (stations[i+1] - w) - (stations[i] + w) - 1;

1초과 n 미만의 조건을 삭제하였다. 아랫줄의 조건으로 그냥 처음과 마지막 기지국 사이에 추가 할 기지국만 생각하고 이어 나오는 if 문 두개에서 체크 못한곳을 마저 체크해주었다.

 

.

.

.

어려웡 ㅜ