[LeetCode] 2914. Minimum Number of Changes to Make Binary String Beautiful

https://leetcode.com/problems/minimum-number-of-changes-to-make-binary-string-beautiful/description/?envType=daily-question&envId=2024-11-05

leetcode - Minimum Number of Changes to Make Binary String Beautiful

문제 유형: 문자열 처리, 그리디

문제 난이도: Medium

 

문제

You are given a 0-indexed binary string s having an even length.

A string is beautiful if it's possible to partition it into one or more substrings such that:

• Each substring has an even length.
• Each substring contains only 1's or only 0's.

You can change any character in s to 0 or 1.

Return the minimum number of changes required to make the string s beautiful.

 

0-indexed의 이진 문자열 s가 짝수 길이로 주어진다.

만약 짝수길이이고 오직 1로만 또는 0으로만 되어있는 부분문자열로 1개 이상 나눌 수 있다면, 아름다운 문자열이다.

아름답게 하기 위해, 최소 변환횟수를 구하시오.

한 번에 한 비트를 바꿀 수 있습니다.

 

풀이

서브스트링을 길이가 2인것만으로 고려해도 된다. 서브스트링의 길이를 늘린다고 더 적은 변환이 필요한 것은 아니다.

또한 2개씩 비교하면 수를 구하기 용이하다.

서브트르링을 2로 고려해서, 두 비트가 다르면 1씩 누적한다. 이를 순차적으로 진행한다.

 

최종 누적을 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minChanges(string s) {
        int n = s.size();
        int ans = 0;
        for(int i = 0; i < n; i += 2) {
            if(s[i] != s[i+1]) ans++;
        }

        return ans;
    }
};