LeetCode No.1529 (F)

LeetCode No.1529 Minimum Suffix Flips

길이가 n인 이진 스트링 target이 주어진다. 0이 n개 있는 초기 스트링에서 target과 같아지려면 몇 번의 동작을 수행해야 하는지 반환하시오.

---

동작의 조건

• 인덱스 i의 비트를 골라서 바꿀 수 있다.
• 단, i 이후 나오는 모든 비트가 바뀐다.
• 예제
  Input: target = "10111"
  Output: 3
  Explanation: Initially, s = "00000".
  Choose index i = 2: "00000" -> "00111"
  Choose index i = 0: "00111" -> "11000"
  Choose index i = 1: "11000" -> "10111"
  We need at least 3 flip operations to form target.

제한 범위

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

---

처음 내 생각

• 어떤 규칙이 있을까 고민해보고, 예제 답안을 통해 규칙성을 유추해 보았다.
• 상술한 예시에서는 인덱스를 아무렇게나 골랐지만, 사실 앞에서부터 바꾸어도 똑같다는 것을 깨달았다.
• 00000 - 11111 - 10000 - 10111로 총 세 번만 바꾸면 된다. 이는 주어진 답과 같다.
• 또한 다른 예시 케이스도 이 법칙이 통용되었다. 이에 기반해 코드를 작성해보았다.

class Solution:
    def minFlips(self, target: str) -> int:
        result = 0
        s = ["0"] * len(target)
        
        for i in range(len(target)):
            if s[i] != target[i]:
                for j in range(i, len(s)):
                    if s[j] == "0":
                        s[j] = "1"
                    else:
                        s[j] = "0"
                result += 1
            
        return result

---

문제점

• n의 자릿수가 10만개까지 나올 수 있다는 제한 사항 때문에, 역시나, 시간 제한에 걸렸다.
• 배열을 만들고, 숫자를 바꿔야 할 때마다 해당 인덱스 미만의 인덱스를 하나하나 찾았기 때문에, O(n^2)만큼의 시간이 걸린다.
• 스스로 걸어 둔 제한 시간이 지나서 추가적인 방법론을 시도해보지 못했다.

---

참고한 링크

• 매우 간결하게 해결한 코드를 발견했다.

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

• 자릿수 하나하나 신경쓸 것 없이, 단지 달라지는 지점에서만 체크한다.
• 또한 바뀐 비트를 체크해주기 위해 start를 지정했다.
• 이렇게 하면 O(n)의 시간 복잡도만 들이고도 답안을 도출할 수 있다.

---

반영하여 다시 푼 코드

class Solution:
    def minFlips(self, target: str) -> int:
        result = 0
        bit = "0"
        
        for i in range(len(target)):
            if bit != target[i]:
                result += 1
                if bit == "0":
                    bit = "1"
                else:
                    bit = "0"
        
        return result

• 참고 코드에서는 어차피 target이 0과 1뿐이라는 점을 응용해 비트를 바꿔 줬다.
• 하지만 내가 풀 때는 또 그 부분은 생각나지 않아서, 인덱스를 따라 훑으면서 비트가 바뀌면 바뀐 것을 따로 적용해줬다.
• 결과적으로 통과!