[알고리즘] 문자열 뒤집기

문제

0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

0001100

이해

뒤집는 횟수를 세려면?

앞글자와 뒷글자가 다른 문자인 경우를 뒤집는 시점이라고 생각하자
0001100 이 문자열에서는 3번째 숫자가 0이고 4번째 숫자 1이므로 이때를 뒤집는 시점이라고 생각한다 👉🏻 count += 1

• 모두 0으로 바꾸는 경우
  • 앞글자가 0 뒷글자가 1일때 👉🏻 0으로 뒤집는 횟수 += 1
• 모두 1으로 바꾸는 경우
  • 앞글자가 1 뒷글자가 0일때 👉🏻 1으로 뒤집는 횟수 += 1

첫글자를 뒤집으려면?

• 모두 0으로 바꾸는 경우
  • 첫글자가 1이면 👉🏻 0으로 뒤집는 횟수 += 1
• 모두 1으로 바꾸는 경우 👉🏻 1으로 뒤집는 횟수 += 1
  • 첫글자가 0

최솟 횟수를 구하려면?

모두 0 또는 1이 되는 경우의 뒤집는 횟수를 세서 더 작은 수를 반환한다
Math.min을 사용하자

계획

1. 모두 0 혹은 1으로 만들기위해 뒤집는 횟수를 저장할 공간을 만든다
   • 0으로 만들기위해 뒤집는 횟수 => countToAllZero
   • 1으로 만들기위해 뒤집는 횟수 => countToAllOne
2. 첫글자가 0인 경우는 countToAllOne, 1인 경우는 countToAllZero에 + 1을 해준다
3. 입력받은 문자열을 순회한다
4. 현재 문자열과 바로 다음 순번의 문자열이 다른 경우 뒤집는 빈도수에 + 1을 더해준다
   • 다음 순번의 문자열이 0일 경우 👉🏻 countToAllOne += 1
   • 다음 순번의 문자열이 1일 경우 👉🏻 countToAllZero += 1
5. countToAllOne과 countToAllZero중 더 작은 값을 반환한다

function findCountToTurnOutToAllZeroOrAllOne(string) {
  const numbers = string.split('');

  let countToAllOne = 0;
  let countToAllZero = 0;

  const addCount = (string) => {
    const method = {
      '0' : () => countToAllOne += 1,
      '1' : () => countToAllZero += 1,
    }

    method[string]();
  }

  addCount(numbers[0]);

  
  numbers.forEach((number, index) => {
    const nextNumber = numbers[index + 1];

    if(!nextNumber) {
      return;
    }
    
    if(number !== nextNumber) {
      addCount(nextNumber);
    }
  });

  return Math.min(countToAllOne, countToAllZero);
}

파이썬

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0
    count_to_all_one = 0

    if string[0] == '0':
        count_to_all_one += 1
    elif string[0] == '1':
        count_to_all_zero += 1

    for i in range(len(string) - 1):
        if string[i] != string[i + 1]:
            if string[i + 1] == '0':
                count_to_all_one += 1
            if string[i + 1] == '1':
                count_to_all_zero += 1

    return min(count_to_all_one, count_to_all_zero)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)