<Algorithm> 171. 기지국설치(Programmers)

기지국설치(Programmers)

   사용 알고리즘 : 그리디 

• 코드는 간결하지만 다른 어려운 BFS, DFS 문제들보다 더 어려운 것 같다. 되게 사고력이 필요한 문제 인 것 같다.
• 다른 코드를 참조해서 풀었는데 이런 부류의 문제들을 많이 풀어봐야 할 것 같다.
• 인덱스를 이용하지 않고 배열을 만든다던가 하면 시간초과가 발생했다. 시간에 대한 제약이 푸는데 힌트가 될수 도 있을 것 같다.

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution {     public int solution(int n, int[] stations, int w) {         int ans = 0;         int idx = 0;         int location = 1;         /****************************          * 기지국의 위치가 최적이 되려면          * 기지국과 최대한 겹치지 않고 모든 범위를           * 사용하는 것이 가장 최적의 선택이 된다.           *           * ex)          *             * l   <  p  >          <  p          * ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ          * 1  2  3  4  5  6  7 8  9 10 11          *           * 가장 왼쪽부터 스타트한다. 현재 위치가          * 가장 가까운 p의 영역에 있는지 아닌지를          * 판단한다.영역에 있지 않기 때문에          * 설치하는 최적의 경우는 모든 영역을          * 쓸수 있는 곳이므로 l은 2에 설치하고          * 4로 넘어가는 것이 최적이다. 4에          * 도착했으므로 p의 영역에 있게 되므로          * 설치할 필요가 없다.그러므로 6으로          * 이동시켜주면된다. 이를 반복하여          * 최적의 갯수를 구할 수 있다.          ****************************/         while(location<=n) {             if(idx<stations.length && location >= stations[idx]-w) {                 location = stations[idx]+w+1;                 idx++;             }else {                 location += 2*w+1;                 ans++;             }         }         return ans;     } } Colored by Color Scripter

cs

 

 

참고 & 출처  

https://healthydeveloper.tistory.com/39?category=675593