2379. Minimum Recolors to Get K Consecutive Black Blocks

https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/?envType=daily-question&envId=2025-03-08

문제 설명

먼저, 이 함수가 해결하려는 문제를 간단히 정리해 보겠습니다.

• 입력:
  • blocks: 'B'(검은색)와 'W'(흰색)로 이루어진 문자열 (예: "WBBWWWBB")
  • k: 연속된 k개의 블록을 선택하려는 길이 (예: 4)
• 목표: 연속된 k개의 블록을 모두 'B'(검은색)로 만들기 위해, 'W'를 'B'로 바꿔야 하는 최소 횟수를 구하는 것.

예를 들어, blocks = "WBBWWWBB", k = 4라면, 길이 4인 연속된 구간(예: "WBBW", "BBWW", "BWWW" 등) 중에서 'W'를 'B'로 바꾸는 횟수가 가장 적은 경우를 찾아야 합니다.

 

문제 풀이

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        # 첫 번째 윈도우의 'W' 개수 계산
        count = blocks[:k].count('W')
        mininmum = count
        # 윈도우를 한 칸씩 이동하며 업데이트
        for i in range(k, len(blocks)):
            if blocks[i - k] == 'W':  # 빠지는 문자
                count -= 1
            if blocks[i] == 'W':      # 새로 들어오는 문자
                count += 1
            mininmum = min(mininmum, count)
        return mininmum

 

1. 첫 번째 윈도우 설정:
   • blocks[:k].count('W'): 문자열의 처음 k개 블록에서 'W'의 개수를 셉니다. 이 값은 첫 번째 구간의 변환 횟수가 됩니다.
   • 예: blocks = "WBBWWWBB", k = 4라면 "WBBW"에서 'W'가 2개이므로 count = 2.
   • mininmum을 이 값으로 초기화합니다.
2. 윈도우 이동:
   • for i in range(k, len(blocks)): 윈도우를 한 칸씩 오른쪽으로 이동하며 업데이트합니다.
   • 이동할 때마다:
     • blocks[i - k]: 윈도우에서 빠지는 맨 왼쪽 문자 확인.
     • blocks[i]: 윈도우에 새로 들어오는 맨 오른쪽 문자 확인.
3. 'W' 개수 갱신:
   • 빠지는 문자가 'W'라면 count를 1 감소시킵니다.
   • 새로 들어오는 문자가 'W'라면 count를 1 증가시킵니다.
   • 이렇게 하면 매번 전체 구간을 다시 세지 않고도 'W'의 개수를 효율적으로 유지할 수 있습니다.
4. 최소값 갱신:
   • 이동할 때마다 mininmum을 현재 count와 비교해 더 작은 값으로 업데이트합니다.
5. 결과 반환:
   • 모든 가능한 구간을 확인한 후, mininmum이 최소 변환 횟수로 반환됩니다.