[백준] 1439_ 그리디, 문자열

✔︎ 문제:

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

1439번: 뒤집기

 

✏️ 나의 풀이

0과 1의 연속적인 구간을 덩어리로 묶었을 때, 더 작은 덩어리 개수인 것을 출력하는 아이디어로 구현

- 문자열에서 숫자가 바뀌는 구간을 딕셔너리에 저장하고, 0과 1 둘중에 더 작은 값을 출력한다. 

- 0에서 1로 바뀔 때 check[0] += 1, 1에서 0으로 바뀔 때 check[1] += 1 로 값을 더해준다.
ex) 000110 일 때,

1) 0 -> check[0] = 0, check[0] = 0

2) 0 -> check[0] = 0, check[0] = 0

3) 0 -> check[0] = 0, check[0] = 0

4) 1 -> check[0] = 1,  check[0] = 0

5) 1 -> check[0] = 1,  check[0] = 0

6) 0 -> check[0] = 1,  check[1] = 1

- 위 연산을 진행한 후, 딕셔너리가 비었다면 0을 출력하고 아니라면 마지막 값을 딕셔너리에 추가한다.

마지막 0: check[0] = 2, check[1] = 1

- 두 딕셔너리 값 중, 작은 것 출력

from collections import defaultdict

s = input()
check = defaultdict(int)
flag = [False, False]

for i in s:
    if i == "0":
        if flag[1] == True:
            flag = [True, False]
            check[1] += 1
            continue
        flag[0] = True
    else:
        if flag[0] == True:
            flag = [False, True]
            check[0] += 1
            continue
        flag[1] = True
if len(check) == 0:
    print(0)
else:
    if flag[0]:
        check[0] += 1
    else:
        check[1] += 1
    print(min(check.values()))

 

 📌 다른 풀이

- 위 과정을 단 몇줄로 깔끔하게 표현할 수 있었다..

- 결국 현재 값과 다음 값을 비교하여 다르다면 카운트 해주면 된다. ex) 000110 -> 3번째에서 4번째, 5번째에서 6번째 총 2개

- 그리고 바껴야하는 덩어리는 3구간이고 여기서 하나의 숫자만 바꾸면 되기 때문에 2로 나눠준다.

S = input()
count = 0
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        count += 1
print((count + 1) // 2)