[Algorithm/Swift] 프로그래머스(Lv.3) - 기지국 설치

안녕하세요 제인입니다:) 꽤나 오랜만이죠..? 인간이 왤케 게으를까요

오랜만에 티스토리를 들어왔더니 피드에 새 글이 엄청 많네요.. 다들 꾸준한 기록 대단해..본받겠습니다..

덕분에 저도 자극받고 다시 열심히 티스토리 글을 열심히 쪄보려고 합니다!!!! 

오늘은 PS 기록을 남겨보려고 하는데 갑자기 Lv3..? 티스토리에 풀이기록은 안했지만.. 머 풀다보니 레벨3까지 왔네요?

레벨3 문제를 풀다보니 확실히 특정 알고리즘을 사용해야하거나, 효율성까지 고려해야하는 문제가 많아서 기록의 필요성을 느꼈습니다.

그래서 앞으로 문제 풀이과정에서 새로 알게 되는 좋은 접근 방법이나 풀이 방법들을 글로 남겨보려고 합니다!

저의 PS 효율성을 위해 문제에 대한 설명은 생략하고 접근 및 풀이 위주로 기록해나가도록 할게요🙃🙂

문제 링크

프로그래머스

문제 풀이

일단 구현 문제긴 한데.. 제한사항이 아래와 같기 때문에 효율성을 고려해야만 하는 문제였습니다.

제한사항
- N: 200,000,000 이하의 자연수
- stations의 크기: 10,000 이하의 자연수
- stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
- W: 10,000 이하의 자연수

 

그렇기 때문에 크기가 N인 배열을 만들어 인덱스 하나하나를 확인할 수는 없겠다고 판단한 후, stations 배열을 순회하며 먼저 전파가 도달하는 곳들을 제외하고 중간중간 전파가 닿지 않는 구간이 어딘지를 파악해서 새로 증설해야 할 기지국 개수의 최솟값을 구해야겠다고 판단했습니다. 여기까지는 잘 접근했던 것 같은데.. 기지국 개수의 최솟값을 구하는 아이디어가 잘 떠오르지 않아 다른 풀이들을 참고해서 해결했습니다..🥲

아이디어

새로 증설해야 할 기지국 개수의 최솟값을 구하는 아이디어는 전파가 도달하지 않는 구간의 거리를 이용하는 것입니다.

하나의 기지국당 커버할 수 있는 구간은 w*2+1 입니다. (기지국에서 양쪽으로 w만큼 떨어진 곳까지 커버가능하고, 기지국이 설치된 곳또 포함되어야하므로 + 1) 이를 이용하면 전파가 닿지 않는 구간의 거리 / (w*2+1) 라는 식으로 설치해야할 기지국 개수의 최솟값을 구할 수 있습니다. 이 때, 나누어 떨어지지 않는다면 커버할 수 없는 구간이 생긴다는 것이기 때문에 기지국 개수를 +1 해주어야 함을 고려해서 코드를 짜주어야 합니다! 전파가 도달하지 않는 구간의 거리는 기지국이 설치된 아파트의 번호가 담긴 배열인 [stations]를 순회하며 구하면 되는데, [stations]의 마지막 요소가 N이 아닐 경우(=마지막 아파트가 아닐 경우)에는 오른쪽에 전파가 도달하지 않는 구간이 남아있다는 것이므로 [stations] 순회 종료 후에 추가적인 기지국 설치가 더 필요한지 확인하는 과정이 필요합니다.

1. [stations]를 순회하면서 전파가 도달하지 않는 구간의 거리 구하기 
2. 1에서 구한 거리 / (w*2+1) 로 해당 구간에 설치해야 할 기지국 개수의 최솟값 구하기 (나누어 떨어지지 않는 경우 +1)
3. [stations] 순회 종료 후 마지막 인덱스가 마지막 아파트 번호가 아닌 경우 추가적으로 기지국 설치

Swift 풀이 코드

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int {
    var answer = 0
    var leftStart = 1
    
    for station in stations {
        // 전파 닿지 않는 왼쪽 거리 구해서 해당 거리 커버할 수 있는 기지국 최소 개수 구하기
        if leftStart < station - w {
            let leftEnd = station - w
            let length = leftEnd - leftStart
            
            if length % (w*2+1) == 0 {
                answer += length / (w*2+1)
            } else {
                answer += length / (w*2+1) + 1
            }
        }
        leftStart = station + w + 1 // 왼쪽 시작점 갱신
    }
    
    let last = stations[stations.count-1]
    
    // 오른쪽에 전파 닿지 않는 부분이 남으면
    if last + w + 1 <= n {
        leftStart = last + w + 1
        
        let leftEnd = n+1 // 인덱스 0부터 시작하니까 1 더해줌
        let length = leftEnd - leftStart
        
        if length % (w*2+1) == 0 {
            answer += length / (w*2+1)
        } else {
            answer += length / (w*2+1) + 1
        }
    }
    
    return answer
}

 

---

[참고 자료]

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