[백준] - 문자열 뒤집기(1439)/파이썬

문제 링크

https://www.acmicpc.net/problem/1439

문제

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

예를 들어 S=0001100 일 때,

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

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

input = "011110"

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    # 이 부분을 채워보세요!
    return 1

result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

---

정답 풀이

1. 0에서 1을 마주쳤을 때 → 전체를 0으로 만들기 위한 작업
2. 1에서 0을 마주쳤을 때 → 전체를 1로 만들기 위한 작업
3. 모든것을 0으로 ,1로 만드는 횟수 저장 변수 선언
4. for 문 범위 : 0번째 인덱스 ~ 문자열의 맨 뒤에서 앞까지
   1. i → 0 부터 문자열의 길이 -2 까지
   2. 현재 인덱스가 다음에 있는 인덱스와 다르면 뒤집어야 하는 포인트
      1. 다음에 있는 인덱스가 1 → 1을 뒤집어야 함 → count_to_all_zero +1
      2. 다음에 있는 인덱스가 0 → 0을 뒤집어야 함 → count_to_all_one +1
5. 위 for 문은 첫번째 숫자를 고려하지 않았으므로
   1. 첫번째 숫자가 0 이면 count_to_all_one +1
   2. 첫번째 숫자가 1 이면 count_to_all_zero +1

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] == "1":
                count_to_all_zero +=1
            if string[i + 1] == "0":
                count_to_all_one += 1

    print(count_to_all_zero,count_to_all_one)
    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)

문제를 풀고 알게 된 개념 및 소감

• min(a,b) : 둘 중 작은 값을 반환해주는 함수