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
뒷글자가 1
일때 👉🏻 0으로 뒤집는 횟수 += 11
뒷글자가 0
일때 👉🏻 1으로 뒤집는 횟수 += 11
이면 👉🏻 0으로 뒤집는 횟수 += 1 0
모두 0
또는 1
이 되는 경우의 뒤집는 횟수를 세서 더 작은 수를 반환한다
Math.min
을 사용하자
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)