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

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

더 자세한 문제 설명은 프로그래머스 기지국 설치 문제를 참고해주세요.

나만의 해결 방법(실패..)

package programmers.lv3;

import java.util.Scanner;

public class BaseStation {

    public int solution(int n, int[] station, int w){
        int answer = 0;

        int[] arr = new int[n+1];

        for(int k : station){

            for(int i = k; i <= k+w; i++){
                if(i <= n){
                    arr[i] = 1;
                }
            }

            for(int i = k-1; i >= k-w; i--){
                if(i > 0){
                    arr[i] = 1;
                }
            }
        }

        for(int i = 1; i <= n; i++){
            int cnt = 1;
            int lt = i;
            if(arr[i] == 0){
                while(cnt <= w*2+1 && lt <= n){
                    if(arr[lt] == 1) break;
                    arr[lt++] = 1;
                    cnt++;
                }
                i = lt-1;
                answer++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        BaseStation T = new BaseStation();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] station = {100000000};
        int w = in.nextInt();

        System.out.println(T.solution(n, station, w));
    }
}

• 주어진 조건에 맞게, station에 주어진 인덱스와, w가 적용된 인덱스의 값을 1로 초기화 시켰다.
• 그 후에 배열을 1~n 까지 돌면서 0인 인덱스가 있다면 그 인덱스부터 w*2+1 인덱스까지 1로 초기화 시키는 로직을 작성했다.
• 정확성은 100%인데 효율성에서 자꾸 실패했다… 그래서 이중for문 문제인가 싶어서 two pointers도 사용해봤는데 소용 없었다.(문제를 해결할 수 있는 로직을 구현하지 못했다..)
• 거의 3시간 넘게 고민하다가, while 문을 거친 인덱스는 모두 1로 초기화되도록 설정해줬으니 그 1 값으로 설정된 인덱스는 if(arr[i] == 0) 인지 확인할 필요가 없어지므로 while 문이 끝나고 나서 i = lt-1 로 설정해줬지만 계속해서 효율성 문제가 발생했다… 정말 미칠 노릇이었다. 시간은 점점 흐르고 있고 포기하고 싶지 않았다. 그래서 5시간 정도를 고민해봤다. 내가 이 문제를 풀 수 있을까?라는 의심이 계속해서 찾아왔다.
• 하지만 다른 문제도 풀어야하고, 코딩테스트 보기 전에 풀었던 문제를 한번 더 복습 해야해서 계속 이 문제만 붙잡고 있는 것은 비효율적이라는 생각에 다른 사람의 풀이를 참고하기로 마음먹었다.. 마음이 씁쓸하다..

다른 사람의 풀이

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

        Arrays.sort(station);

        int leftStart = 1;

        int tmp = w*2+1;

        for(int k : station){
            if(leftStart < k - w) {
                int leftEnd = k - w;

                int length = leftEnd - leftStart;

                int count = length / tmp;
                if (length % tmp != 0) count++;

                answer += count;
            }

            leftStart = k + w + 1;

        }

        if(station[station.length-1] + w + 1 <= n){
            leftStart = station[station.length-1] + w + 1;
            int leftEnd = n+1;

            int length = leftEnd - leftStart;

            int count = length / tmp;
            if(length % tmp != 0) count++;

            answer += count;
        }

        return answer;
    }
}

[출처 : https://small-stap.tistory.com/81]

• station을 기준으로 왼쪽 빈공간을 w2+1로 나눴을 때 나머지가 존재한다면 w2+1로 나눈 값 + 1만큼의 추가 기지국이 필요할 것이다.
• 반대로 station 기준 오른쪽 빈공간이 존재한다면 같은 방식으로 기지국을 설치할 수 있을 것이다.
• 내가 푼 로직은 N개의 아파트를 배열로 만들었었는데 아무래도 그러다 보면, N개만큼 루프문을 돌아야 하기 때문에 효율성에서 실패한 것 같다.

결론(후기)

• 배열이 아닌 다른 방향으로 접근해봤으면 어떨까 싶다.
• 며칠 뒤 코딩테스트만 없었다면 더 여유롭게 문제를 풀어봤을 것 같은데 아쉽다.
• 규칙성을 잘 찾아보는 것이 가장 중요한 것 같다.