[Hackerrank] Goodland Electricity

문제 설명

Goodland에는 일렬로 나열된 여러 도시들이 있습니다. 각 도시는 양 옆 도시와의 거리가 1입니다. 정부는 모든 도시에 전기를 공급하기 위해 최소한의 발전소를 설치하고자 합니다.

• 배열 arr은 각 도시가 발전소 설치에 적합한지 여부를 나타냅니다.
  • 1: 발전소 설치 가능
  • 0: 발전소 설치 불가능
• 발전소는 설치된 위치를 기준으로 좌우로 k - 1칸까지 전기를 공급할 수 있습니다.
• 모든 도시에 전기를 공급하기 위해 필요한 최소 발전소 개수를 구하세요.
• 만약 모든 도시에 전기를 공급할 수 없다면 **-1**을 출력합니다.

---

입력

1. 첫 번째 줄: 두 정수 n(도시의 수)과 k(발전소의 전기 공급 범위)
2. 두 번째 줄: 길이가 n인 배열 arr (발전소 설치 가능 여부)

---

출력

• 모든 도시에 전기를 공급하기 위해 필요한 최소 발전소 개수 출력
• 불가능하면 -1 출력

제약조건

• 1 ≤ k ≤ n ≤ 10^5
• arr[i] ∈ {0, 1}

---

예제 입력 1

 

6

2

0 1 1 1 0 0

예제 출력 1

2

📖 설명

• 1번 위치에 발전소 설치 → 0~2번 도시 전기 공급
• 3번 위치에 발전소 설치 → 2~4번 도시 전기 공급
• 총 2개의 발전소로 모든 도시에 전기 공급 가능

---

예제 입력 2

 

6

2

0 1 0 0 0 0

예제 출력 2

-1

설명

• 1번 위치에 발전소 설치 → 0~2번 도시 전기 공급
• 3번 이후 도시에 발전소를 설치할 수 있는 위치가 없음 → 모든 도시에 전기 공급 불가능

 

문제는 이렇다. 그리디 기법을 사용해야 된다고 생각했고, 우선 왼쪽에서부터 arr이 1인, 발전소가 설치 가능한 지역을 살펴보았다. 그리고 가능한 범위에서 제일 오른쪽에다가 발전소를 세워야지 최소로 발전소를 세울 수 있다고 생각해서, 제일 오른쪽에 발전소를 세운다. i - (k -1)과 i + (k - 1)에서 가장 오른쪽에 발전소를 세우는 방식이 최소한의 발전소를 세우는 방식이다. 만약 범위 내에 커버할 수 없는 발전소가 없다면, -1을 return 하도록 코드를 설계하였다. 그리고 발전소를 설치하고, 탐색 위치를 발전소가 커버 가능한 다음 위치로 옮기는 방식을 이용했다.

정답 코드는 다음과 같다.

def pylons(k, arr):
    n = len(arr)
    i = 0  # 현재 도시 위치
    ans = 0  # 설치한 발전소 수

    while i < n:
        # 현재 위치에서 오른쪽 끝까지, 가능한 가장 오른쪽에 발전소 설치
        pos = min(i + k - 1, n - 1)
        
        # pos부터 왼쪽으로 가면서 발전소 설치 가능한 위치 찾기
        while pos >= i - k + 1 and pos >= 0 and arr[pos] == 0:
            pos -= 1

        # 설치할 수 있는 위치가 없다면 -1 반환
        if pos < i - k + 1 or pos < 0:
            return -1

        # 발전소 설치
        ans += 1

        # 설치 후, 발전소가 커버하는 범위 다음 위치로 이동
        i = pos + k

    return ans