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

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

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

하지만 처음부터 4번째, 5번째 문자열 00을 11로 뒤집으면 한 번만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어질 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력해라

입력조건

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만 보다 작다.

출력조건

• 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력한다.

사고과정

• 예전에 백준 문제에서 풀었던 기억이 있었는데 다시 풀려고 하니 풀지 못했다^^ 직전 문자열이랑 비교함으로써 바뀐 횟수를 기록해야 하나 싶었는데, 그런식으로 하면 '그리디' 문제 유형이 적용되지 않았다. 답도 틀리게 나왔다..
• 시간 내에 풀지 못하고 2개의 풀이를 보았다. 단순히 0을 1로 바꾸는 횟수 1을 0으로 바꾸는 횟수를 각각 기록해서 2개 중 최소값인 것을 출력하면 되는 것이었다.(허무데스~ 아직 갈 길이 멀다~)

풀이(스스로 풀지 못함)

1. 예전에 백준에서 푼 풀이

s = input()
changes = [s[0]]

for i in range(1, len(s)):
	if s[i] != changes[-1]:
    	changes.append(s[i])

zero_cnt = changes.count('0')
one_cnt = changes.count('1')

print(min(zero_cnt, one_cnt))

2. 책 풀이

s = input()
count0 = 0    # 1 -> 0으로 바꾸는 횟수
count1 = 0    # 0 -> 1으로 바꾸는 횟수

if s[0] == '1':
    count0 += 1
else:
    count1 += 1

for i in range(len(s)-1):
    if s[i] != s[i+1]:
        if s[i+1] == '1':
            count0 += 1
        else:
            count1 += 1

res = min(count0, count1)
print(res)