[이코테] Greedy 문제 - 3. 문자열 뒤집기

문제 :  0과 1로 된 문자열에서 연속된 숫자를 뒤집어 같은 숫자로 만들기

 

실패)

line = [int(i) for i in list(input())]
index_list = []
gini = 1.0 - line.count(0)/len(line) * line.count(1)/len(line)
result = 0
while gini != 1.0:
    index = [0,0]
    for i in range(len(line)-1):
        if line[i] == line[i + 1]:
            index[1] += 1
        else:
            index_list.append(index)
            index = [i+1,i+1]
    index_list.append(index)
    print(index_list)
    index = min(index_list, key=(lambda i: i[1]-i[0]))
    line[index[0]:index[1]+1] = [1-a for a in line[index[0]:index[1]+1]]

    gini = 1.0 - line.count(0)/len(line) * line.count(1)/len(line)

    index_list = []
    result += 1

print(result)

뻘짓했다(...)

쉬운 방법을 생각 못하고 쓸데없이 어렵게 생각하다가 완전 말아먹음.

 

정답)

line = [int(i) for i in list(input())]
result = 0
count0 = 0 #0으로 바뀌는 횟수
count1 = 0 #1로 바뀌는 횟수

if line[0]: #시작이 1이면
    count0 += 1 #0으로 바뀜
else:
    count1 += 1

for i in range(len(line)-1):
    if line[i] != line[i+1]: #다르면
        if line[i+1]: #0->1
            count0 += 1
        else: #1->0
            count1 += 1
    #print(count0, count1)
result = min(count1, count0)

print(result)

쉬운거였는데 엄청 해맸다. 끙...