[알고리즘]그리디_문자열 뒤집기(파이썬 min함수)

[문자열 뒤집기 문제 설명]

-난이도 : ★☆☆

-풀이시간 : 20분

-시간 제한 : 2초

-메모리 제한 : 128MB

-기출 : 핵심 유형

-출처 : 이것이 코딩테스트다 with 파이썬(p.313)

 

-문제 : 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 뒤집는 것을 1을 0으로, 0을 1로 바꾸는 것을 의미합니다. 

예를 들어 S=0001100일 때는 다음과 같습니다.

 

1. 전체를 뒤집으면 1110011이 됩니다.

2. 4번째 문자부터 5번째 문자까지 뒤집으면 111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있습니다.

 

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

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하세요. 

 

입력조건 : 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다.

출력조건 : 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력합니다. 

-입력예시 0001100

-출력예시 1

 

 

 

[문자열 뒤집기 답안1]

#data를 입력받는다.
data = input()
case0=0 #1을 0으로 바꾸는 경우 count
case1=0 #0을 1로 바꾸는 경우 count

#첫번째 원소 처리하기
if data[0] == '1' : #1을 0으로 뒤집는 경우이므로 case0에 count
    case0 +=1
else: #0을 1로 바꾸는 경우이므로 case1 에 count
    case1 +=1


#두번째 원소부터 모든 원소를 확인한다.
for i in range(len(data)-1) : #i는 0부터 (사용자가 입력한 수-1)
    if data[i] != data[i+1] :
        if data[i] == '1' :
            case0 +=1
        else :
            case1 +=1

print(min(case0, case1))

 

[답안1 설명]