[코테] 99클럽 코테 스터디 30일차 TIL - 문자열

Question1 - [미들러] 최소한의 플립 (Minimum Suffix Flips)

 

문제 설명 https://leetcode.com/problems/minimum-suffix-flips/description/

 

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.

 

Example 1:

• 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.

Explanation: We do not need any operations since the initial s already equals target.

 

Constraints:

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

---

문제풀이

 

trial1

오늘의 문제는 'flip'의 의미를 잘 파악한다면 생각보다 코드를 간단히 할 수 있는 문제였다.

 

길이가 n인 문자열인 target이 주어지고, 

'flip'이라는 기능은 특정 index부터 문자열의 끝까지 문자열을 바꾸는 (0은 1로, 1은 0으로) 기능이다.

n길이에 0으로만 구성된 s가, 최소한의 flip만을 거쳐 target이 되려면, 몇번 flip해야 하는지를 구하는 문제.

 

예시를 잘 살펴보면, "00000"를  "10111"로 만들기 위해서는 총 세번의 flip이 필요하다.

"00000" ->  "11111" (index = 0)   : 1로 변경 

 "11111" -> "10000" (index = 1)    : 0으로 변경

"10000" -> "10111" (index = 2)    : 1로 변경 

 

즉, 첫번째 자리부터 문자열을 flip해 나가는데, 이때 flip 해야 할, 변경 해야할 문자도 달라진다. (1->0 -> 1) 

이 변경 대상이 되는 문자를 current로 변수를 따로 두고, 

첫째 자리부터 돌면서 해당 자리 문자가 current와 같으면 그대로 두고, current와 다르다면 flip으로 문자열을 바꿔준다.

문자열을 바꿀때마다 count +1, current 업데이트를 해주면 된다.

class Solution(object): 
	def minFlips(self, target): 
    	n = len(target)
        count = 0
        current = '0'
        
        for i in ragne(n): 
        	if target[i] != current : 
            	count += 1
                current = target[i]
        
        return count