[그리디 알고리즘3] 백준 1439 뒤집기 파이썬

백준 1439 뒤집기 

 

📜 문제 

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

예를 들어 S=0001100 일 때,

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

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

 

🚩 입력 

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

 

🌞 출력

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

 

 

🍟문제 풀이 

사실 요 문제 접근부터 틀려서 오~ 랫 동안 고민했었다. 결국 다른 분들의 코드를 보면서 풀게 되었는데 생각보다 너무 간단해서 현타가 왔었다. 

 

푸는 방법은 입력받은 string을 for문을 돌려서 0 -> 1 or 1 -> 0 이렇게 바뀔 때만 count += 1 을 해준다. count는 변화했던 횟수를 담고 있고 매번 변화할 때마다 다솜이는 바꿀 필요가 없다. 0 또는 1 둘 중 하나로만 바꾸면 되기 때문에 //2 나누기 2만 해주면 된다.   (count + 1) //2   +1 을 하는 이유는 

 

입력받은 string -> 변화 횟수 -> 뒤집어야할 횟수 

# 0 -> 0 -> 0 

# 01 -> 1 -> 1

# 010 -> 2 -> 1

# 0101 -> 3 -> 2

# 01010 -> 4 -> 2

# 010101 -> 5 -> 3

 

요렇게 보면 변화 횟수(count)에 + 1을 하고 몫만 가져오면 뒤집어야할 횟수가 나온다. 

 

 

🥕 정답 코드 

s = input()

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

print((cnt+1)//2)

for문을 돌릴 때 i와 i+1의 요소를 비교할 것이기 때문에 len(s)-1로 해주어야 한다. 그냥 len(s)로 하면 error : out of index 리스트 index가 맞지않는다는 오류가 뜬다. 

 

 

다른 사람 코드 

s = input()
cnt = 0 
prev='?'

for i in s:
    if i != prev:
        prev=i
        cnt += 1

print((cnt)//2)

prev= '?' 로 설정하고 string의 가장 처음 i 가 0이든 1이든 cnt += 1로 만들어서 print할 때 +1을 할 필요가 없다.