프로그래머스 - 기지국 설치(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=java

 

[문제 설명]

기지국을 최소한으로 설치해서 모두가 인터넷을 할 수 있게 해줘라.

 

[접근 방법]

문제 언어가 Java밖에 없어서 오랜만에 Java를 사용해서 풀었다.

문제를 봤을 때, 딱 그리디 냄새가 나는 문제.

단, 문제의 조건으로 아파트의 개수가 N: 200,000,000이다.

나는 처음에 O(N)에 방법이 생각나서 이 방법으로 풀었는데 효율성을 통과하지 못했다.

제출하면서도 N이 2억인데 이게 효율성이 되나? 싶었는데 걱정하던대로 효율성을 하나도 통과 못했다.

 

따라서, 단순하게 길이를 이용하여 푸는 방법을 선택했다.

결국, 기지국이 없는 거리를 측정하고 그 사이에 기지국을 몇 개 세울지만 알면 된다.

않은 면적이 핵심

 

 

[처음 작성한 오답 : 시간초과 ]

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

        for (int station : stations) {
            checkConnected(isConnected, station - 1, w);
        }

        int cntOfUnconnectedCity = 0;
        for (int i = 0; i < n; i++) {
            if (!isConnected[i]) {
                cntOfUnconnectedCity++;
            } else {
                if (cntOfUnconnectedCity != 0) {
                    answer += getBaseStationCntNeeded(cntOfUnconnectedCity, w);
                }
                cntOfUnconnectedCity = 0;
            }
        }

        if (cntOfUnconnectedCity != 0) {
            answer += getBaseStationCntNeeded(cntOfUnconnectedCity, w);
        }

        return answer;
    }

    private void checkConnected(boolean[] isConnected, int station, int w) {
        for (int i = station - w; i <= station + w; i++) {
            if (i < 0) {
                continue;
            } else if (isConnected.length <= i) {
                break;
            }

            isConnected[i] = true;
        }
    }

    private int getBaseStationCntNeeded(int cntOfUnconnectedCity, int w) {
        int cnt = 0;
        cnt += cntOfUnconnectedCity / (w * 2 + 1);
        if (cntOfUnconnectedCity % (w * 2 + 1) != 0) {
            cnt++;
        }

        return cnt;
    }
}

[수정 코드]

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int start = 0;
        int end = 0;
        
        for (int station : stations) {
            int stationPosition = station - 1;

            end = stationPosition - w - 1;

            if (end < start) {
                end = start;
            } else {
                answer += getBaseStationCntNeeded(start, end, w);
            }

            start = stationPosition + w + 1;
            if (start >= n) {
                break;
            }
        }

        if (start <= n - 1) {
            answer += getBaseStationCntNeeded(start, n - 1, w);
        }

        return answer;
    }

    private int getBaseStationCntNeeded(int start, int end, int w) {
        int cnt = 0;
        int cntOfUnconnectedCity = end - start + 1;
        cnt += cntOfUnconnectedCity / (w * 2 + 1);
        if (cntOfUnconnectedCity % (w * 2 + 1) != 0) {
            cnt++;
        }

        return cnt;
    }
}

 

[느낀 점]

현실에서 코딩을 할 때, 매 번 생각하는 게 '이 코드보다 효율적인 코드가 있을까?'다.

알고리즘을 풀 때는, 보통 자료의 개수의 한계를 정해주고 시간제한을 주므로 단순하게 시간복잡도만 계산해서 문제를 풀고는 한다.

이번 문제는 이러한 시간 제한을 안줘서 더 효율적인 방법이 있는데도 이를 생각하지 못하고, 쉬운 방법을 택했다.

쉬운 방법이 있더라도 늘 더  효율적인 코드를 작성하도록 노력하자.