2914. Minimum Number of Changes to Make Binary String Beautiful

Problem : https://leetcode.com/problems/minimum-number-of-changes-to-make-binary-string-beautiful

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:08:22

 

---

 

문제 설명

 

 

0-인덱스의, 짝수 길이의 이진 문자열 s가 주어진다.

 

어떤 문자열이 아름답다는 것은 다음 조건을 만족하는 하나 이상의 부분문자열들로 나눠질 수 있음을 의미한다.

 

• 각 부분 문자열은 짝수 길이이며
• 각 부분 문자열은 0 혹은 1로만 주어진다.

문자열의 어떤 문자든 0이나 1로 바꿀 수 있다.
문자열 s를 아름답게 하기 위해 필요한 최소 변환 횟수를 반환하라.

---

 

풀이

 

언뜻 보면 DP냐, 분할정복이냐.. 꽤 고민할 수 있지만, 문제 자체를 좀 더 심도 있게 파헤쳐보면 더 간단한 문제임을 알 수 있다.

 

조건을 만족하는 부분문자열의 길이는 제한이 없다. 즉 부분 문자열을 모두 1, 0으로 만드는 문제로 접근하지 말고, 최소 길이 2인 부분 문자열이 모두 '11', '00'이 되도록 하는 문제로 바꾸어 생각해 보자.

 

그럼 한 번의 순회로 문제를 풀 수 있다. 각 짝수 인덱스 i에 대해서, i+1번째 문자와 일치하는지 여부만을 살피면 되기 때문이다. 만약 일치하지 않는다면 적어도 한 번의 변환이 필요하므로 1을 더해주면 끝.

 

문제를 어떻게 자기 식으로 해석하고 풀이할 수 있는지를 요구하는 문제. 테크닉보다는 창의성이 필요했다.

 

 

풀이 코드

class Solution:
    def minChanges(self, s: str) -> int:
        result = 0
        for i in range(0, len(s), 2) :
            if s[i] != s[i+1] :
                result += 1
        return result