[LeetCode] 2379. Minimum Recolors to Get K Consecutive Black Blocks (Python)

Problem

Solution

string
sliding window

 

blocks string에서 연속된 B의 개수가 k개가 될 수 있도록 가장 최소한의 변경해야되는 W 수를 구하는 문제.

substring에서 힌트를 얻어서 k길이만큼 substring을 구하고 W의 개수를 구한뒤 가장 최소값을 리턴하였다.

 

나는 구현으로 일일이 string을 검사하는 방식으로 풀이했는데 슬라이딩 윈도우 기법을 사용하면 더 최적화된 알고리즘 O(N)으로 해결할 수 있다.

 

Code

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        n = len(blocks)
        answer = 999
        if 'W' in blocks and n == k:
            count = 0
            for i in range(n):
                if blocks[i] == 'W':
                    count += 1
            return count

        for i in range(n):
            if i+k <= n:
                sub_str = blocks[i:i+k]
                count = 0
                for j in range(len(sub_str)):
                    if sub_str[j] == 'W':
                        count += 1
                print(sub_str, count)
                answer = min(answer, count)
        return answer

 

<다른 풀이>

def minimumRecolors(blocks: str, k: int) -> int:
    min_flips = float('inf')
    w_count = 0
    
    # 초기 윈도우 설정
    for i in range(k):
        if blocks[i] == 'W':
            w_count += 1
    min_flips = w_count
    
    # 슬라이딩 윈도우 적용
    for i in range(k, len(blocks)):
        if blocks[i - k] == 'W':  # 윈도우에서 벗어나는 부분
            w_count -= 1
        if blocks[i] == 'W':  # 새로 포함되는 부분
            w_count += 1
        min_flips = min(min_flips, w_count)
    
    return min_flips

 

Complexity

Time Complexity

첫번째 for문에서 O(N)

두번쨰 for문에서 O(K)

최종 시간복잡도 : O(N * K)

 

Space Complexity

sub_str = blocks[i:i+k] 이므로 공간복잡도는 O(K)