[LeetCode] 1758. Minimum Changes To Make Alternating Binary String

https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string/description/

Minimum Changes To Make Alternating Binary String - LeetCode

leetcode - Minimum Changes To Make Alternating Binary String

문제 유형 : 비트마스킹, 수학

문제 난이도 : Easy

 

문제

You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.

Return the minimum number of operations needed to make s alternating.

 

당신은 문자열 s를 받습니다. 바이너리 형태(0또는 1)로 이루어져 있고, 한 번의 연산을 통해 0을 1로 또는 1을 0으로 바꿀 수 있습니다.

인접한 두 문자들이 서로 다르면 문자열은 교차한다고 불립니다. 예를 들어서, 문자열 010은 교차하고, 0100은 아닙니다.

 

S를 교차하는 문자열로 만들기 위한 최소 연산 수를 구하시오.

 

풀이

두 가지의 케이스를 구해야 한다.

0으로 시작하는 경우 - 01010101...

1로 시작하는 경우 - 10101010...

 

문자열을 1회 순회하면서 짝수 번째 인덱스에 0이 오거나, 홀수 번째 인덱스에 1이 오면 카운트를 1씩 증가시킨다.

이 카운트가 1로 시작하는 경우의 필요한 연산 횟수이다.

S의 길이 - 1로 시작하는 경우의 연산횟수 = 0으로 시작하는 경우의 연산횟수이다.

 

두 횟수 중에서 더 작은 수를 반환시킨다.

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minOperations(string s) {
        const int n = s.size();

        int ops10 = 0;
        for(int i = 0; i < n; i++) {
            if(s[i]-'0' == i%2) ops10++;
        }

        return min(ops10, n-ops10);
    }
};