문자열 뒤집기

[문자열 뒤집기]

0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다.

할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다.

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 

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

"011110"

 

---

알고리즘 문제를 풀다보면, 문제 자체를 이해하기 힘들 때가 있습니다. 그럴 때는 다음과 같이 해보세요!

 

1. 바로 코드를 작성하지 말고, 문제의 다른 예시들을 떠올리면서 규칙성을 생각해보세요.

    ex) 00000 은 최소 횟수를 어떻게 구할까?

2. 배웠던 자료구조를 활용하면 어떨지 생각해보세요!

    ex) 스택, 큐를 활용하면 어떨까?

3. 문제의 특징들을 하나하나 글로 써보세요!

    ex) 문자열을 뒤집어야 하는데, 0으로 할지 1으로 할지 고민 된다.

        뒤집는 걸 감지할만한 시점은 0에서 1로, 1에서 0으로 바뀌는 시점인데,

        초기에 0인지 1인지도 횟수에 연관이 있다.

---

 

[규칙성 파악하기]
모두 0으로 만드는 방법에서 최소로 뒤집는 횟수: count_to_all_zero
0 -> 1로 문자열이 전환되는 순간 count_to_all_zero += 1
모두 1로 만드는 방법에서 최소로 뒤집는 횟수: count_to_all_one
1 -> 0으로 문자열이 전환되는 순간 count_to_all_one += 1

1) 뒤집어질 때, 즉 0 -> 1 또는 1 -> 0으로 바뀔 때 횟수 추가
2) 첫 번째 원소가 0인지 1인지에 따라서 횟수 추가

input = "0011001100"


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] == "1":
        count_to_all_zero += 1
    elif string[0] == "0":
        count_to_all_one += 1
    for i in range(len(string) - 1):
        if string[i] != string[i + 1]:
            if string[i + 1] == "1":
                count_to_all_zero += 1
            elif string[i + 1] == "0":
                count_to_all_one += 1
    return min(count_to_all_zero, count_to_all_one)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

 

 

내가 푼거

input = "0011001100"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_zero = 0
    count_to_one = 0
    if string[0] == "1":
        count_to_zero += 1
    if string[0] == "0":
        count_to_one += 1
    for i in range(len(string)-1):
        if string[i] == "0" and string[i+1] == "1":
            count_to_zero += 1
        if string[i] == "1" and string[i+1] == "0":
            count_to_one += 1
    if count_to_zero < count_to_one:
        return count_to_zero
    return count_to_one


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)