C++ 프로그래머스 코딩테스트 - 기지국 설치 (12979)

기지국 설치

Level 3

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

프로그래머스

 

 

 

기지국을 추가 설치해서 모든 아파트에 전달해야한다.

 

 

 

 

기지국을 최소로 설치하면서 모든 아파트에 전파를 전달한다.

위의 예시에서는 최소 3개를 설치하면 모든 아파트에 전달 가능하다.

 

 

 

나의 풀이

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

	for (int appart : stations)
	{
		int leftIdx = appart - w - 1;
		if (leftIdx > lastRightIdx)
		{
			leftIdx -= lastRightIdx;
			int need_5G_cnt = leftIdx / (w * 2 + 1);
			if (leftIdx % (w * 2 + 1) != 0)
				need_5G_cnt += 1;
			answer += need_5G_cnt;
		}
		lastRightIdx = appart + w ;
	}
	if (n > lastRightIdx)
	{
		n -= lastRightIdx;
		int need_5G_cnt = n / (w * 2 + 1);
		if (n % (w * 2 + 1) != 0)
			need_5G_cnt += 1;
		answer += need_5G_cnt;
	}
	return answer;
}

 

 

 

풀이 요점

처음에는 0 ~ 아파트 개수 만큼 for문을 돌았는데, 효율성 체크에서 통과하지 못했다. O(N) = 아파트 개수

그래서 stations 를 for문을 돌도록 변경했다. O(N) = 현재 기지국 개수 (stations 개수)