[Programmers] 기지국 설치 - Summer/Winter Coding(~2018) (Greedy 알고리즘)

3186 단어 algorithmalgorithm
// 기지국 설치 - Summer/Winter Coding(~2018) (Greedy 알고리즘)
public class BaseStationInstall {
	public int solution(int n, int[] stations, int w) {
		int answer = 0, pos = 1, s = 0;
		while (pos <= n) {
			if (s < stations.length && pos >= stations[s] - w) {
				pos = stations[s] + w + 1;
				s++;
			} else {
				pos += 2 * w + 1;
				answer++;
			}
		}
		return answer;
	}
}
  • O(n) 으로 Greedy 알고리즘 구현

좋은 웹페이지 즐겨찾기