2379. Minimum Recolors to Get K Consecutive Black Blocks

Problem : https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks

 

Difficulty : Easy

 

Status : Solved

 

Time : 00:11:15

 

---

 

문제 설명

 

길이 n의 blocks 문자열이 주어집니다. blocks[i]는 'W' 혹은 'B'이며, i번째 block의 색상을 의미합니다. 'W'와 'B'는 각각 흰색과 검은색을 의미합니다.

 

또한 정수 k가 주어지며, 연속적인 검은 블록의 목표 개수를 의미합니다.

 

한 번의 작업에서, 당신은 흰색 블록이 검은색 블록이 되도록 바꿀 수 있습니다.

 

최소한 하나 이상의 k개의 연속적인 블록들이 나타나도록 필요한 최소 작업 개수를 반환하세요.

---

 

풀이

 

다시 오랫만의 풀이. 간단하게 생각해 볼 필요가 있다.

 

브루트포스로 접근해 보자. 우리는 길이 k개의 모든 블록 개수를 확인해 볼 것이다(n-k개의 경우의 수가 있을 것이다). 그리고 그 k개의 블록이 모두 검은 색이 되도록 하면 된다. 이 때의 작업 개수는 해당하는 블록들 중 흰색 블록의 개수가 된다. 가장 원시적인 방법으로 풀어보면 다음과 같이 작업이 이루어진다.

 

• 0 ~ k-1번째 블록에서 흰색 블록을 센다.
• 1 ~ k번째 블록에서 흰색 블록을 센다.
• ...

 

이 때의 시간 복잡도는 O(nk)이다.

물론 우리는 첫 번째 작업, 두 번째 작업 ... n-k번째 작업을 전부 다 할 필요는 없다. 잘 생각해 보면, 첫 번째 작업과 두 번째 작업은 공통 작업 구간(1, k-1)이 있지 않는가? 그렇다면, 두 번째 작업을 처음부터 시작하는 대신 첫 번째 작업의 결과를 그대로 재활용하면 된다. 1 ~ k-1개의 흰색 블록 개수를 기억하고, 0번 블록이 흰색 블록인지, k번 블록이 흰색 블록인지만을 판단하면 된다. 이런 식의 재활용을 수행할 경우, 시간복잡도는 O(n)이 된다.

 

 

풀이 코드

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        ans = len(blocks)

        whites = 0
        bcount = 0
        for i in range(len(blocks)):
            if blocks[i] == 'W':
                whites += 1
            bcount += 1
            if bcount > k:
                bcount -= 1
                if blocks[i-k] == 'W':
                    whites -= 1
            if bcount == k:
                ans = min(ans, whites)
        return ans