[프로그래머스 Summer/Winter Coding(~2018)] 기지국 설치 -Java

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

코딩테스트 연습 - 기지국 설치

 

class Solution {
		public int solution(int n, int[] stations, int w) {
			int answer = 0;

			int start = 1, right = 0, left = 0, empty;
			for (int i = 0; i < stations.length; i++) {
				left = stations[i] - w; //전파범위 왼쪽 끝
				right = stations[i] + w; //전파범위 오른쪽 끝

				empty = left - start; //왼쪽에 빈공간 구해주기
				if (empty > 0) { // 왼쪽 비었으면
					answer+=build(empty,w); //몇개 설치 ?
				}
				start = right + 1;
			}

			if (start == n) answer += 1; //끝이 16인데 start가 16이면 1개 설치
			else if (start < n) { // 맨 마지막 오른쪽 범위 남았으면
				empty = n - start + 1;
				answer+=build(empty,w);
			}
			return answer;
		}

		private int build(int empty, int w) {
			int result=empty / (2 * w + 1); //나누어 떨어지면 딱 그 개수만큼
			if (empty % (2 * w + 1) == 0)  return result; //안나누어 떨어지면 +1
			else return result+1;
		}
	}

소요시간 : 30분

 

제한사항을 봤을 때 배열을 만들어서 풀거나 완전탐색으로 풀면 분명 통과가 안될거라고 생각했습니다. 

그래서 이분탐색 or 그리디로 문제를 접근했습니다.

 

이렇게 생각한 후에 문제에 접근하니 아이디어가 쉽게 떠올랐습니다.

하나의 기지국을 기준으로 왼쪽 부분이 비어있는지만 확인합니다. 전파의 범위는(2w+1)입니다. 

왼쪽 부분이 비어있는지 확인하기 위해서 

우선 stations배열을 하나씩 순회합니다. 

하나의 stations를 얻었을 때 left(왼쪽 전파 끝부분) , right(오른쪽 전파 끝부분) , empty(left-start)를 구해줍니다.

만약 stations[i]=4 이고, w=2라면  left = 2 (4-2) , right = 6(4+2) , empty = 1 ( 2-1) 이 나옵니다! 

이때 empty크기를 통해서 몇개의 기지국을 설치해야하는지 구해서 answer에 더해줍니다.

그리고 하나의 stations를 다 돌면 마지막에 start=right+1을 줍니다. 

그 이유는 다음 stations[i]를 얻을 때 왼쪽이 비어있는지 확인할려면 기준점이 필요한데 그 기준점 역활을 start가 해줍니다!

 

그리고 모든 stations을 순회한 뒤 start값을 통해 마지막 기지국을 기준으로 오른쪽에 비어있는 공간이 있는지 확인하고 있다면 empty를 통해 기지국을 설치해줍니다!