Lv3. [그리디] - 기지국 설치하기

---

[ 문제 링크 ]

프로그래머스 Lv3. 기지국 설치하기

 

[ 문제 설명 이미지 ]

 

탐욕법

1. 현재(초기) 위치에서부터 모든 아파트를 순회한다.
2. 현재 위치가 전파범위에 속하는지 확인하고 전파 범위가 아니라면 일단 기지국을 세운다.
   이때, 전파 범위의 효과가 최대가 되도록 전파 유효범위 만큼 이동하여 기지국을 설치한다.
3. 전파가 끝나는 지점 이후부터 한칸씩 이동하면서 기지국을 설치한다.
   설치 도중, 만약 이미 세워진 기지국의 점파범위 안으로 들어갈 경우 일단 해당 위치에도 설치한다.
4. 다음 위치로 이동했는데, 이미 설치되어있는 기지국의 전파범위에 포함된다면 기지국의 범위 바깥으로 이동한다.
5. 벗어난 뒤 계속해서 마지막 아파트까지 같은 작업을 반복한다.

[풀이 1] Queue사용

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

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

        Queue<Integer> stationsQueue = new LinkedList<>();
        for (int station:stations) stationsQueue.offer(station);
        int curPosition = 1;
        while (curPosition <= n) {
            if (!stationsQueue.isEmpty() && stationsQueue.peek() - w<= curPosition) {
                curPosition = stationsQueue.poll() + w+1;
            } else {
                answer += 1;
                curPosition += w*2+1;
            }
        }
        return answer;
    }
}

 

우선 자료구조 Queue를 사용하기 위해 Queue자료구조를 LinkedList를 이용해 선언한다.

foreach loop를(향상된 for문) 통해 배열에 저장된 각 기지국을 생성한 Queue객체에 offer메소드를 통해 순차적으로 추가한다.

 

이후 while문을 통해 현재 위치부터 마지막 위치까지 루프를 돈다.

 

만약 현재 기지국을 기준으로 좌측범위 끝이 현재위치보다 작거나 같은 경우

앞서 while문을 통해 현재 위치가 한칸씩 넘어가다가 기지국 범위내에 존재하는것 이므로

이는 기지국을 설치할 수 없으니 기지국 바깥으로 이동시킨다.

if (!stationsQueue.isEmpty() && stationsQueue.peek() - w <= curPosition) {
    curPosition = stationsQueue.poll() + w+1; //기지국 바깥으로 이동
}

 

그 경우가 아니라면 answer값을 1 증가시키고 현재 설치한 기지국의 끝범위 만큼 현재 위치를 이동한다

else {
    answer += 1;
    curPosition += w*2+1;
}

 

 

 

테스트 케이스에서는 모두 성공했으나,

효율성 테스트에스는 모두 실패했다.

보통 효율성 테스트에서 시간을 제일 많이 잡아먹는 부분은 Loop이다.

그러나 Loop에는 문제가 없다.

두번째 원인을 생각해보면 자료구조이다.

Queue자료구조 사용으로 인해 기본적으로Wrapper형태의 Object 자료구조이기 때문에

발생한 문제이다.

Queue자료구조를 사용하지 않고 배열 그 자체로 기지국에 접근하도록 구현해야 한다.

 

 

 

---

[풀이 2] 배열 그 자체로 기지국 접근

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

        int curPosition = 1;
        int stationIndex = 0;
        while (curPosition <= n) {
            if (stationIndex < stations.length && stations[stationIndex] - w<= curPosition) {
                curPosition = stations[stationIndex] + w+1;
                ++stationIndex;
            } else {
                answer += 1;
                curPosition += w*2+1;
            }
        }
        return answer;
    }
}

 

stations배열에 접근하기 위해 index를 초기화해준다.

int stationIndex = 0;

 

if조건문에서 Queue가 비어있지 않은 조건과 현재 위치가 기지국 왼쪽범위 안에 포함되는지 에 대한 조건을 배열인덱스와 길이로 처리한다.

if (stationIndex < stations.length && stations[stationIndex] - w <= curPosition)

또한 if문 내부에서 현재위치를 현재 기지국의 우측 범위끝 바깥으로 초기화하는 코드 또한 배열의 index로 접근한 뒤,

해당 index를 1 증가시키도록 처리한다.

if (stationIndex < stations.length && stations[stationIndex] - w <= curPosition) {
    curPosition = stations[stationIndex] + w+1;
    ++stationIndex;
}

---

 

 

[나의 풀이] 몫 과 나머지

public class Solution {

    int answer, coverage = 0;

    public int solution(int n, int[] stations, int w) {

        coverage = w*2+1;

        int curPosition = 1; // 현재 위치를 저장
        for (int station : stations) {
            //필요 기지국 갯수계산: 기준거리=현재 기지국의 왼쪽 끝 범위 - 현재 위치
            getAnswer((station - w) - curPosition);
            curPosition = (station + w) + 1; // 현재 기지국 우측바깥 위치(기지국의 우측 끝 + 1)를 현재위치에 저장
        }
        // 기지국 루프 종료 후 현재 위치가 아파트 끝 번호보다 작거나 같으면 최소 한개의 아파트가 남아있다는 뜻
        if (curPosition <= n) getAnswer(n-curPosition+1); //필요 기지국 갯수계산: 기준거리=마지막 아파트부터 현재 위치까지의 거리

        return answer;
    }

    public void getAnswer(int interval) {// 나눴을때 몫이 1 혹은 나머지가 1이면 answer 증가
        int quotient = interval / coverage; // 몫
        if (quotient > 0) answer += quotient;// 몫이 1보다 크면 몫만큼 증가
        if (interval % coverage > 0) ++answer;// 나머지가 1보다 크면
    }
}

 

현재 위치부터 기지국의  왼쪽 끝범위의 거리를 구하고,

해당 거리 기준으로 기지국의 범위만큼 나누었을때

 

몫만큼 answer를 증가시키고 추가로 나머지가 있다면 answer를 1증가시킨다.

 

증가 종료 후 현재 대상 기지국 범위가 끝나는 새로운 위치에서 거리를 다시 구해야 하므로

현재 위치를 우측 바깥 위치로 초기화한다.

 

이후 기지국에 대한 루프가 종료되었을 때, 만약 현재 위치가 마지막 아파트보다 작거나 같을경우

마지막 아파트부터 현재 위치까지의 거리로 answer를 한번 더 계산해준다.

 

 

이는 한번씩 들리는것보다 몫으로 나누어서 몫만큼 증가시키는게 더 효율적이라고 생각 해서 구현했다.

하지만 시간복잡도에서 for문의 횟수는 상수를 1로 취급하기 때문에 거의 엇비슷한 시간이 측정된다.

(나눗셈,몫에 대한 연산 시간도 포함되는것같음.)