99클럽 코테 스터디 28일차 TIL/ minimum-suffix-flips

minimum-suffix-flips

학습 키워드: 루프, 문자열
문제 링크: https://leetcode.com/problems/minimum-suffix-flips/description/

문제 설명

주어진 길이 n의 0-인덱스 이진 문자열 target이 있습니다. 초기에 모든 비트가 '0'인 길이 n의 이진 문자열 s가 있습니다. 우리는 s를 target과 같아지도록 만들려고 합니다.

한 번의 작업에서는 인덱스 i를 선택할 수 있으며, 이때 [i, n-1] 범위의 모든 비트를 뒤집을 수 있습니다. 뒤집기는 '0'을 '1'로, '1'을 '0'으로 변경하는 것을 의미합니다.

s를 target과 같아지도록 만들기 위해 필요한 최소 작업 횟수를 반환하는 함수를 작성해야 합니다.

제한 조건

• n == target.length
• 1 <= n <= 105
• target[i] is either '0' or '1'.

문제 풀이

i부터 끝까지의 문자열을 뒤집는 것이기 때문에 뒤에서부터 탐색해 줌.

class Solution:
    def minFlips(self, target: str) -> int:
        n = len(target)
        flipCount = 0
        s = ['0'] * n
        
        for i in range(n-1, -1, -1):
            if s[i] != target[i]:
                flipCount += 1
                # 범위 [0, i]를 뒤집음
                for j in range(i+1):
                    s[j] = '1' if s[j] == '0' else '0'
        
        return flipCount

        

코멘트