[이코테/Python] 그리디 - 문자열 뒤집기

이것이 코딩 테스트다 with python

그리디 문자열 뒤집기(Python)

문제

0과 1로만 이루어진 문자열 S가 있다.
연속된 숫자를 잡고 뒤집을 수 있다.(0을 1로, 1로 0으로)
모두 같은 수를 만들 수 있는 뒤집기의 최소 횟수를 구하라.

• 예시

입력 : ‘00001110000’
결과 : 1

풀이

0과1이 인접한 부분이 몇개 있는지를 체크하면 된다. 예를들어 인접한 부분의 패턴을 ‘01’을 조사한다. 하지만, 1010 문자열을 조사하게 되면 마지막 인접한 부분을 조사하지 못해 최소 횟수가 1이 되므로 마지막 문자열에 1을 붙여주고 조사한다. 이렇게만 진행했을 경우 ‘010’을 조사하게 되면 최소 횟수가 2회가 된다. 그렇기 때문에 같은 방법으로 ‘01’과 ‘10’을 둘다 조사하여 두가지의 최소 횟수중 최소값을 구한다.

1. 문자열 S(str)의 마지막 부분을 조사해서 0 또는 1을 붙여준다.
2. 반복문을 돌며 ‘01’패턴과 ‘10’패턴을 조사한다 각각의 횟수를 count_0, count_1에 저장한다.
3. count_0과 count_1중 최소값을 return한다.

코드

    def solution(str):
        if str[-1] == '1':
            str += '0'
        else:
            str += '1'
        count_0 = 0
        count_1 = 0
    
        for i in range(len(str)-1):
            if str[i]+str[i+1] == '01':
                count_0 += 1
            if str[i]+str[i+1] == '10':
                count_1 +=1
    
        return min(count_0,count_1)
    
    
    
    if __name__ == "__main__":
        str = "010"
        print(solution(str))