백준 1439 - 뒤집기

내용

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

풀이

문제에 대한 가장 가까운 근접해를 찾아야 한다.(Greedy) 문제를 살펴 봤을 때 0과 1 중에서 가장 적게 등장하는 빈도의 수를 뒤집어서 통일 된 수를 만들면 해결되는 문제

잘못된 접근 1

처음 문제를 풀었을 때는 0과 1을 각각 카운팅해서 적게 나오는 수를 뒤집으면 해결된다고 생각했다. 하지만 그렇게 문제를 접근할 경우 몇번 뒤집어야 하는지에 대해 해답을 줄 수 없다.
그렇기 때문에 예를들어 0001100이 있을 때 각각의 수를 카운팅하는 것이 아닌 연속으로 등장하는 공통된 수를 하나로 묶어서 카운팅하고, 카운팅 한 0,1 묶음 중에서 가장 작은 값을 해답으로 결정한다.

ex)

0001100 : [[000],[00]] --> 2개 || [[11]] --> 1개
따라서 1을 뒤집어야한다 (정답 1)

잘못된 접근 2

위의 방법대로 해결하기 위해서 연속된 숫자끼리 배열을 만들어서 추가하려고 했지만 시간 소요가 생각보다 많이 나온다. 생각하던 도중 연속된 수 한번 카운트를 추가하고 그 뒤 같은 숫자라면 continue를 이용하여 넘기고 다른 숫자가 등장하면 해당 숫자를 다시 카운트 시키는 방식을 이용하고 마지막에 min을 이용하여 가장 작은 값을 이용하는 방식을 사용했다.

ex)

0001100: 000 => 0 카운터 +1 || 11 => 1 카운터 +1 || 00 => 0 카운터 +1

소스코드

import sys

S = sys.stdin.readline().rstrip()
result = 0
zero_cnt = 0
one_cnt = 0
if S.count("0") == 0 or S.count("1") == 0:
    print(0)
else:
    for i in range(len(S)):
        if i == 0:
            if S[i] == "0":
                zero_cnt += 1
            else:
                one_cnt += 1
            continue
        if S[i-1] == S[i]:
            continue
        if S[i-1] != S[i]:
            if S[i-1] == "0":
                one_cnt += 1
            else:
                zero_cnt += 1

    print(min(zero_cnt,one_cnt))