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

https://school.programmers.co.kr/learn/courses/30/lessons/12979#

프로그래머스

 

접근

---

• 예제 1을 기준으로 할 때 커버 가능한 범위가 중요한 것이지, 1번에 기지국을 설치하는지/2번에 기지국을 설치하는지는 중요하지 않다
  → 설치될 인덱스에 집중하지 않아도 된다
• 현재 설치된 아파트를 기준으로 기지국이 설치되어야 하는 범위들을 나누고, 범위의 길이를 통해 각 범위마다 설치되어야 최소 개수를 더한다 (범위가 2인데 가용 범위가 3일 경우, 1개만 설치되면 되기 때문)

 

로직

---

• stations에 대해 반복문을 수행하면서, 현재 설치된 아파트와 가용 범위를 제거한 새로 설치되어야 하는 범위를 구한다
• 각 범위의 길이(end-start)를 가용 범위 (2*w+1)로 나눈 몫을 answer에 더한다
• 각 범위의 길이(end-start)를 가용 범위로 (2*w+1)로 나눴을 때 나머지가 0이 아닌 경우에만 answer에 1을 더해준다
  • 3 % 3 == 0, 1개만 설치되어도 된다
  • 4 % 3 == 1, 2개가 설치되어야 한다

코드

---

1. Swift 풀이

---

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    
    var range = [(Int, Int)]()
    for i in 0..<stations.count {
        var start = 1
        if i > 0 {
            start = stations[i-1] + w + 1
        }
        let end = stations[i] - w - 1
        range.append((start, end))
    }
    if stations.last! != n {
        range.append((stations.last!+w+1,n))
    }

    var answer = 0
    for (s, e) in range {
        answer += (e-s+1) / (2*w+1)
        if (e-s+1) % (2*w+1) > 0 {
            answer += 1
        }
    }
    return answer
}

 

2. Python 풀이

---

def solution(n, stations, w):
    
    answer = 0
    start = 1
    
    for s in stations:
        
        end = s-w-1
        answer += (end-start+1) // (2*w+1)
        
        if (end-start+1) % (2*w+1) != 0:
            answer += 1
            
        start = s+w+1
    
    if start <= n:
        
        answer += (n-start+1) // (2*w+1)
        
        if (n-start+1) % (2*w+1) != 0:
            answer += 1
    
    return answer