[java] 프로그래머스 - 기지국 설치

문제

프로그래머스-기지국 설치
N개의 아파트에 전파를 전달하기위해 최소로 설치해야할 기지국의 수를 구하는 문제

• 제한 사항
  아파트 수 N: 200,000,000 이하의 자연수
  이미 설치된 기지국 정보, stations의 크기: 10,000 이하의 자연수
  stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수
  전파의 도달거리 W : 10,000 이하의 자연수

풀이

N의 크기를 보고 효율성 문제인 것을 직감했다
stations배열을 돌면서 전파가 통하는 왼쪽(start)과 현재 위치까지 범위에 몇개의 기지국을 설치해야하는지 구하는 식으로 풀었다

문제 예시1번처럼 N = 11, stations={4,11}, w = 1이라고 한다면 초기상황은 그림과 같다

1. 현재위치 curr : curr = 1
   한 기지국의 전파범위 총합 cv = 2 * w + 1 = 5
2. stations를 하나씩 불러오는데, 처음 stations[0] = 4이다
3. 기지국 전파범위 왼쪽 start : stations[0] - w = 3
4. 기지국 전파범위 오른쪽 end : stations[0] + w = 5
5. curr >= start이면, 현재위치는 이미 전파가 통하는 곳이므로 curr = end + 1로 갱신한다
   5-1. 2로 돌아간다
6. (start - curr) % cv의 값을 계산한다
   6-1. 나머지가 0이라면, 해당 범위에 맞춰 기지국이 들어가므로 정답에 (start-curr) / cv를 추가한다
   6-1. 나머지가 0이 아니라면, 여분의 칸이 있다는 뜻이므로, 정답에 (start-curr) / cv + 1을 추가한다

시행착오 (시간초과)

시간초과의 원인에 대해 생각보다 한참을 고민했다
위의 풀이에는 적지않았는데 원인은 생각보다 의외였다
바로 Math.ceil((start - curr) / cv)을 썼기 때문이었다 (또르르)
ceil을 쓰고 안쓰고의 시간 차이는 약 10배였다..
나는 분명 O(N)의 시간을 쓴 것 같은데 왜 시간이 터지는지 내 속도 터지고 있었다
친구가 “야 혹시 ceil 쓰지말아봐”했는데 통과해서 조금 허망했다
Math.ceil을 열어봤는데 생각보다 단계도 많고, 내용이 복잡했다
가급적 라이브러리를 안쓰도록 해야겠다..

소스코드

class Solution {
public int solution(int n, int[] stations, int w) {
		int answer = 0;
		int cv = w * 2 + 1;
		int curr = 1;
		int start = 1;
		int end = 1;
		int diff = 0;
		for (int i = 0; i < stations.length; i++) {
			start = stations[i] - w;
			end = stations[i] + w;
			if (curr >= start) {
				curr = end + 1;
			} else {
				diff = start - curr;
				if (diff % cv == 0)
					answer += diff / cv;
				else
					answer += diff / cv + 1;
				curr = end + 1;
			}
		}
		if (curr <= n) {
			diff = n + 1 - curr;
			if (diff % cv == 0)
				answer += diff / cv;
			else
				answer += diff / cv + 1;
		}
		return answer;
	}
}