백준 1439 뒤집기 with Python

 

www.acmicpc.net/problem/1439

1439번: 뒤집기

---

<My code>

s = input()
x_count = 0
for i in range(len(s)-1):
    if s[i] != s[i+1]:
        x_count += 1
        
result = x_count // 2
if x_count % 2 == 1:
    result += 1
print(result)

완전탐색으로 풀기에는 시간복잡도가 너무 커서 규칙을 발견해 그리디하게 풀었다.

 

앞에서부터 하나씩 문자를 비교해 서로 다를 경우 x_count를 +1 해준다.

x_count가

▶홀수일 때는 (x_count // 2) + 1이 정답이 되고

▶짝수일 때는 x_count // 2 가 정답이 된다.

---

<Reference Code>

s = input()
count0 = 0
count1 = 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
            
print(min(count0, count1))

문자열을

▶모두 0으로 바꿨을 때의 개수와

▶모두 1로 바꿨을 때의 개수를 비교해 그 중 작은 값을 결과값으로 하는 풀이다.