[99클럽 코테 스터디 30일차 TIL] LeetCode | 1529. Minimum Suffix Flips

30일차 string

Problem

https://leetcode.com/problems/minimum-suffix-flips/

 

Sol

초기 '0'으로만 이루어진 문자열 s의 특정 인덱스 i부터 n-1까지 flip 했을때 '0'과 '1'로 이루어진 target과 똑같아 질 수 있는 최소 flip 수를 세는 문제

 

해결 방법

👀 처음에 단순하게 생각해서 그냥 반복문으로 풀었습니다. for문이 안팎으로 돌다보니까 최소의 수를 보장할 수도 없고 시간복잡도가 O(n^2)이 나오는 효율 바닥 코드가 나왔습니다. 혹시나 했는데 역시나 test case는 통과했지만 submit을 하니까 Time Limit Exceeded가 떴습니다. T.T

 

 

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

 

---

 

 

👀 그래서 시간을 들이고 다시 처음부터 생각해보았습니다. 문자를 실제로 뒤집는 것이 아니라, 연산의 횟수를 아는 것이 목표입니다. 0과 1을 비트로 바라보고 target과 비교하며 변경이 필요한 지점의 수를 카운트하는 방식으로 해결하였습니다.

class Solution:
    def minFlips(self, target: str) -> int:
        flip_cnt = 0
        s = '0'  # 초기 상태는 '0'

        for char in target:
            if char != s:
                flip_cnt += 1
                s = char  # 현재 상태를 target의 현재 비트로 업데이트
        
        return flip_cnt

 

 

1. s 초기화 : 초기 상태 s는 모두 '0'

2. target 순회 : 처음부터 끝까지 순회하면서 target의 비트와 s의 비트를 비교
 ⭐ 실제로 비트를 뒤집는 대신, 비트가 뒤집혀야 하는 지점 찾아내는 과정

3. 다르다면, 이 지점에서 비트를 flip 해야한다는 의미
 • flip_cnt += 1
 • s를 target의 비트로 업데이트 : flip된 상태 반영

 

 

이렇게 하였을때도 어쨌든 s의 첫 인덱스부터 차근차근 target과 비교하기 때문에 "최소의 카운트를 보장할 수 있는가?"  하는 의문이 들었습니다. 그래서 나의 개비스콘 chatGPT에게 물어보았습니다.

 

 

chatGPT의 답변에서 알 수 있었던 것

• 문제의 본질
  • 이 문제의 핵심은 단순히 'target'의 비트가 바뀌는 지점을 찾는 것
  • s가 target과 다를 때마다 flip이 필요
    ∴ 비트의 변화가 있는 지점을 찾아내기만 하면 되므로, 순서가 역순이든 순방향이든 상관 없음
• 앞에서부터 탐색해도 최소 횟수가 보장되는 이유
  1. 변경 지점 : 비트가 바뀌는 지점에서만 flip 필요
  2. 연속된 플립 : 한 번 flip을 하면 그 이후의 비트들은 자동으로 연속된 flip
  3. 역방향으로 탐색할 경우도 변경 지점 동일

 

시간복잡도 O(n)

• n개의 target 비트 확인 : O(n)

 

---

💬 소감

 문제의 본질을 제대로 이해하지 못했었습니다. 하지만 조금만 생각해보면 해결할 수 있는 문제였습니다. 사실 그 생각이라는 게 제일 어려운 것 같아요.