[백준] 1439번 : 뒤집기

출처 : 이것이 취업을 위한 코딩테스트다 p.313

문제 출처 : https://www.acmicpc.net/problem/1439

참고 : https://codingpractices.tistory.com/72

 

유형 : 그리디, 정렬

 

1. 문제

 

예시

11001100110011000001

예시 출력

4

---

2. 풀이1

data = input()

count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

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

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

print(min(count0, count1))

이 풀이의 경우 1) 전부 0으로 바꾸는 경우 2) 전부 1로 바꾸는 경우 모두 따져서 둘 중 더 적은 횟수를 가지는 경우를 계산하였다. 현재 숫자랑 다음 위치의 숫자를 비교해서 다음 숫자가 1이면 count1을 증가, 0이면 count0을 증가하는 방식을 이용하였다. 그런데 이 경우는 두 가지 모두를 따지기 떄문에 다음 풀이 방법이 더 효율적이라고 생각한다.

 

3. 풀이 2

data = input()
cnt = 0
for i in range(len(data)-1):
    if s[i] != s[i+1]:
        cnt += 1

print((cnt+1)//2)

수가 변화할 때마다 cnt를 증가시키고 이 변화 횟수를 마지막에 계산 처리를 해준다. 

 

(cnt+1) // 2를 하는 이유는 다음과 같다.

data	변화 횟수	뒤집어야 하는 횟수
0	0	0
01	1	1
010	2	1
0101	3	2
01010	4	2
010101	5	3

이 변화에 맞게 식을 세우면 cnt+1에서 2를 나눈 몫이 뒤집어야 하는 횟수가 된다.