프로그래머스[Java] - 기지국 설치(그리디)

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

코딩테스트 연습 - 기지국 설치 | 프로그래머스

시간 초과 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
	public int solution(int n, int[] stations, int w) {
		int answer = 0;	// 기지국의 갯수
		
		Queue<Integer> sq = new LinkedList<Integer>();
		for(int s : stations) {
			sq.offer(s);	// 현재 기지국이 설치된 아파트 추가
		}
	
		int position = 1;	// 아파트 1동부터 끝까지 
		while(position <= n) {	// 동 전체을 돌면서
			
			// 기존에 설치된 기지국이 존재해야하고,
			// 현재의 위치(position)가 기존 설치된 기지국(sq.peek())의 전파 범위(w) 안에 있는지 확인
			if(!sq.isEmpty() && position >= sq.peek() - w) {
				// 다음 이동해야 할 포지션
				position = sq.poll() + w + 1;	// 기지국의 오른쪽 끝
 			}
			else {
				answer += 1;	// 기지국 하나 설치
				
				// 기지국 설치에 의해 발생하는 최대 전파범위
				// 왼쪽 전파범위 + 기지국설치(1) + 오른쪽 전파범위
				position += (w*2) + 1;
			}
		}
		
		return answer;
	}
}

위 코드는 테스트 케이스는 전부 맞지만 시간초과가 발생하는 코드이다.

시간 초과?(효율성테스트) => 더 빠르게 동작하도록 프로그램을 바꾼다.

 

Tip. 효율성 높이기

1. Loop 개선

2. 적절한 데이터 구조 사용

3. 불필요한 오브젝트 제거

 

최종 코드

public int solution(int n, int[] stations, int w) {
	int answer = 0;	// 기지국의 갯수
	int si = 0;	// station의 인덱스
	int position = 1;	// 아파트 1동부터 끝까지 
	while(position <= n) {	// 동 전체을 돌면서	
    
		// 기지국이 설치된(stations 배열의 요소가 존재할 때 까지) 곳 까지만 탐색
                // 현재의 위치(posotion)가 기존 설치된 기지국(stations[si])의 전파 범위(w) 안에 있는지 확인
                // 만약 기존 설치된 기지국의 범위 안에 있을경우 => 전파 범위이므로 기지국을 설치할 필요가 없다.
		if(si < stations.length && position >= stations[si] - w) {
			// 다음 이동해야 할 포지션
			position = stations[si] + w + 1;	// 기지국의 오른쪽 끝
			si ++;	// 다음 설치한 기지국을 찾기 위해 인덱스 +1
 		}
		else {
			answer += 1;	// 기지국 하나 설치
			
			// 기지국 설치에 의해 발생하는 최대 전파범위
			// 왼쪽 전파범위 + 기지국설치(1) + 오른쪽 전파범위
			position += (w*2) + 1;
		}
	}
	return answer;
}

Queue 대신 설치된 기지국의 인덱스를 탐색하며 푼 코드 .........

 

 

입출력 예 1번을 보면...

아파트 N  = 11

기존 기지국이 설치된 아파트 stations[] = {4, 11}

전파 거리 W = 1

 

위 에서 1동아파트부터 탐색을 한다.

1동은 기존 설치된 기지국의 범위가 아니므로, 기지국을 설치할 때 발생하는 최대 전파범위를 찾는다.

위에선 2번 아파트에 기지국을 설치하면 아파트(1, 2, 3) 모두 전파범위이므로 최대가 된다.

그 후 탐색할 아파트는 4번부터 탐색하면 된다.

(왼쪽 전파범위(1) + 기지국 설치(2) + 오른쪽 전파범위(3)) = (w*2) + 1

 

 

 

4번 아파트의 경우 기존에 기지국이 설치된 아파트이다.

기존에 기지국이 설치된 아파트의 경우 뛰어넘고, 어느 아파트부터 탐색할지 시작 position을 다시 잡아주면된다.

또한 다음 기지국이 설치된 아파트를 찾기위해 stations의 인덱스 si를 ++한다.

 

 

 

즉 기존에 기지국이 설치된 아파트(4동)에서 전파범위(w)만큼 더한 후, 1을 더해주면 그다음의 탐색시작범위가 된다.

 

다시 6번부터 위의 과정을 반복해서 실행하면 된다 ...

 

전체 아파트를 돌면서 기존에 기지국이 설치된 아파트는 뛰어넘고, 기지국을 어느 아파트에 설치하는게 최소가 되는지 순간순간 최적의 해를 찾는 그리디, 탐욕법 문제

 

코드는 간결하지만 어떻게 저런식으로 생각하고 풀어야할지 막막하다 ......

다음에 다시 풀면 못풀것같지만 더 다양한 문제들 풀고 익히며 다양하게 생각해봐야겠다 ...

 

 

 

틀린 코드

public class Solution{
	
	public static int solution(int n, int[] stations, int w) {
        int answer = 0;
        boolean[] check = new boolean[n+1];
        
        // 기존에 주어진 4g 기지국이 설치된 아파트 체크
        for(int i=0; i<stations.length; i++)
            check[stations[i]] = true;
        
        for(int i=1; i<=w; i++){
            for(int j=0; j<stations.length; j++){
                // 설치된 아파트를 기준으로 좌,우 아파트 기지국 설치
                // 이때, 좌 우에 아파트가 없는경우 => 설치할 수 없음
                if(stations[j]-i >= 1){   // 왼쪽에 아파트가 있는 경우
                    check[stations[j]-i] = true;
                }
                
                if(stations[j]+i <= n){   // 오른쪽에 아파트가 있는 경우
                    check[stations[j]+i] = true;
                }
            }
        }
        
        for(int i=0; i<check.length; i++){
            int count = 0;  // 기지국이 설치된 아파트 전까지 설치되지 않은 아파트의 갯수
            while(!check[i]){
                count ++;
                i ++;
                if(i == n)
                    break;
            }
            
            if(count != 0){ // 기지국을 설치해야 할 아파트가 있는 경우
                /*
                 * w(전파 도달 거리)에 따라 증설해야 할 기지국의 개수가 달라짐.
                 * w=1 => 최대 3개 아파트 설치 가능 (w*2) + 1
                 * w=2 => 최대 5개 아파트 설치 가능 (w*2) + 1
                 * w=3 => 최대 7개 아파트 설치 가능 (w*2) + 1
                */
                int wPlus = (w*2) + 1;  
                
                // 위에서 계산한 w의 규칙만큼 기지국을 설치한다.
                // w=1 --> count가 1, 2, 3 일땐 1개설치
                // w=1 --> count가 4, 5, 6 일땐 2개설치
                double plus = Math.ceil((double)count / wPlus);
                answer += (int)plus;
            }
        }

        return answer;
    }

나의 풀이

N = 아파트의 갯수

stations[] = 현재 기지국이 설치된 아파트의 번호

W = 전파의 도달거리

 

위 세개가 매개변수로 주어진다.

따라서 나는 boolean[]형 check 배열을 통해 아파트의 기지국이 설치됬는지 안됬는지 판단하는 식으로 해결하려 했다.

먼저 현재 기지국이 설치된 stations[]의 아파트 번호를 check 배열에 체크한다.

그 후 현재 기지국이 설치된 좌, 우 아파트에 W 만큼 체크를 표시한다.

(이 때, 현재 설치된 기지국의 좌,우 에 아파트가 없는경우 기지국을 설치할 수 없다.)

 

입출력 예 1번을 들면

N = 11, stations = [4, 11] , W = 1 에서,

첫번째로 check[4] = check[11] = true 로 설정한다.

다음으론 W = 1이므로, 좌 우 한칸씩 true로 표시한다.

check[3] = check[5] = true

check[10] = true (아파트가 11개이므로, check[12] 는 체크할 필요가 없다.)

그 후 기지국이 설치되지 않은(false) 아파트들을 기준으로 몇개의 기지국을 설치해야 하는지 구해준다.

 

이 때, 전파의 도달 거리(W)와 규칙을 찾아봤는데 ...

 

W=1 --> 양옆 한칸씩 기지국을 설치할 수 있으므로 3개가 설치가능하다.

W=2 --> 양옆 두칸씩 기지국을 설치할 수 있으므로 5개가 설치가능하다.

W=n --> 양옆 n 칸씩 기지국을 설치할 수 있으므로 (n*2) +1 개가 설치가능하다.

 

위와 같은 규칙을 통해 W의 숫자에 따라 필요한 기지국의 갯수를 구해준다.

 

 double plus = Math.ceil((double)count / wPlus);

위 문장의 경우,

W=1 일때, 

count가 1~3은 1개,  4~6은 2개, 7~9는 3개의 기지국이 필요하다.

따라서 (w*2)+1로 나눴을때 올림을 해주면 된다.

 

제출하면 테스트케이스도 일부 틀리고,, 시간초과가 나온다 .......... ㅠㅠ

그래서 프로그래머스의 강의를 봤다 .......