[LeetCode] 1529 Minimum Suffix Flips

💡 오늘의 학습 키워드

📌  배열

 

문제 설명

문제 링크 : https://leetcode.com/problems/minimum-suffix-flips/

You are given a 0-indexed binary string target of length n.
You have another binary string s of length n that is initially set to all zeros.
You want to make s equal to target.
In one operation, you can pick an index i where 0 <= i < n 
and flip all bits in the inclusive range [i, n - 1].
Flip means changing '0' to '1' and '1' to '0'.
Return the minimum number of operations needed to make s equal to target.

제한 사항
1. n == target.length
2. 1 <= n <= 10^5
3. target[i] is either '0' or '1'.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

처음 떠올렸던 방법은 완전 탐색을 통한 DFS 풀이였습니다. 비트를 완전 탐색하는 방식으로 재귀적 탐색이 가장 적합하다 생각했지만,
생각보다 탐색 시간이 길고 시간 초과가 발생할 정도로 효율이 좋지 않아 다른 탐색 방식이 필요했습니다.
이 때 필요한 방식이 그리디한 풀이 방식이고 문제 풀이 과정은 다음과 같습니다.

1. 현재와 목표 문자열을 처음부터 끝까지 한 번만 탐색합니다.
2. 현재 문자열과 목표 문자열이 다른 부분이 나오면 그 부분부터 끝까지 뒤집기를 시행합니다.
3. 뒤집기를 수행할 때 연산 횟수를 +1 증가시켜준 후 최종 연산 횟수를 리턴해줍니다.

이렇듯 해당 방법은 DFS를 이용한 완전 탐색이 아니라 실제 문자열을 뒤집지 않고 최소한의 연산 개수를 계산할 수 있게 해줍니다.
이렇게 하면 문자열을 직접 변경하지 않고도 필요한 연산 횟수를 구할 수 있습니다.

 

💡 내가 해결한 방식은?

DFS를 이용한 풀이 (시간 초과)

class Solution:

    def minFlip_1(self, target: str) -> int:
        result = float("inf")

        def dfs(num, s, target, n):
            nonlocal result
            if s == target:
                result = min(result, num)
                return result

            for i in range(num, n):
                flipped = s[:i] + ''.join('1' if x == '0' else '0' for x in s[i:])
                dfs(num+1, flipped, target, n)

        n = len(target)
        s = "0" * n
        dfs(0, s, target, n)
        return result

연산의 홀/짝 상태를 이용한 풀이 

class Solution:
    def minFlips(self, target: str) -> int:
        
        flips = 0
        for b in target:
            if flips % 2 == 1 - int(b):
                flips += 1

        return flips

배열 인덱스를 이용한 풀이

class Solution:
    def minFlips(self, target: str) -> int:
        count = 0
        last = '0'
        
        for ch in target:
            if last != ch:
                count += 1
                last = ch
        
        return count

 

---

✍️ TIL

진짜 이런 문제가 적절한 알고리즘을 떠올리고 이를 사용해 풀이하는 것보다 더 체감 난이도가 크다.
시간 복잡도를 초과하지 않는 방법 중 가장 효율적인 인덱스 이동을 찾아내야 한다.
완전 탐색을 하게 되면 직접적으로 보이는 반면, 이 방식은 보이지 않는 로직을 찾아 보이도록 만들어야 한다.
'last = ch' 부분이 너무 어려우면 다음과 같이 표현해도 좋다.

last = '0' if last == '1' else '1'

뒤집기 연산을 한 이후의 상태를 추적하기 위해 사용되는 만큼 문자열을 직접 변경하지 않고도 연산 횟수를 계산하게 되어
시간 복잡도를 초과하지 않는 효율적인 풀이가 될 수 있는 것이다.