[프로그래머스/Level3] 기지국 설치 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 그리디

 

한 번에 2개의 기지국을 설치할 수 있다.

두 지점 사이에 2w + 1이 몇 개가 들어갈 수 있는지를 계산하면 된다.

(2w+1인 이유 : 양쪽으로 w가 퍼지고, 기지국 1개 포함)

 

현재 위치를 1부터 시작해서

- 현재 위치가 기지국 범위 밖에 있으면, 현재 위치를 포함한 가장 먼 곳에 기지국을 설치하고, 설치한 기지국 밖으로 이동한다.

- 현재 위치가 기지국 범위 안에 있으면, 해당 기지국 범위 밖으로 이동한다.

 

 

 

🔺 코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int now = 1;    // 현재 위치
        int sIdx = 0;   // 기지국 idx
        int answer = 0;
                
        while(now <= n) {
            // 현재 위치가 모든 기지국 범위보다 작으며, 특정 기지국 범위 내에 있는 경우
            if(sIdx < stations.length && now >= stations[sIdx] - w) {
                now = stations[sIdx] + w +1;    // 현재 위치를 해당 기지국 밖 오른쪽으로 이동
                sIdx++; // 계산할 기지국을 다음 기지국으로 변경
            }
            // 현재 위치가 모든 기지국 범위를 벗어난 경우 
            else {
                answer++;
                now += 2*w + 1; // 새로 설치한 기지국 범위 오른쪽에 이동 (겹치는 건 상관x)
            }
        }
 
        return answer;
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

- 이 두 풀이가 좀 비슷하다.

⇒ 거리별 최소 기지국 수 계산 방법 : 거리 범위 % (w * 2 +1)

1. 기존 기지국 범위에 속하지 않는 구역을 구간으로 구분한다. (1~ 1번째 기지국, 기지국 사이 구간, 마지막 기지국~ 구간 끝)
2. 해당 구간을 하나의 기지국 범위(2w +1)로 나눠 올림 적용해 누적합을 계산한다.

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

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

---

💦 어려웠던 점

- 구간마다 이분 탐색을 하게 했는데 틀렸다. 그 이유는 이 글을 통해 알 수 있었다.

 

 

🧐 새로 알게 된 내용

- 요소 하나하나 접근하기 보다, 구간 단위로 접근하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

프로그래머스 - 기지국 설치 문제 (자바)

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

 

[JAVA] 기지국 설치

 

 

- 멋진 그림 설명..

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