[Python] 백준 1439번_뒤집기

https://www.acmicpc.net/problem/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만보다 작음
• 출력
  • 첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력
• 시간 제한: 2초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

(예제 입력 1) 
0001100 -> 1

(예제 입력 2)
11111 -> 0

(예제 입력 3)
00000001 -> 1

(예제 입력 4)
11001100110011000001 -> 4

(예제 입력 5)
11101101 -> 2
"""

 

 

## 의사코드 ##

# 뒤집기 -> 연속된 하나 이상의 숫자만 가능 

# # cur = 0 # 현재 숫자
# # cnt = 0 # 뒤집기 횟수
# for i in s:
#     if i == cur:
#         continue
#     else:
#         cnt += 1 # 뒤집기 횟수 + 1
#         cur = i # 현재 숫자를 i로 변경

# print(cnt//2) # 행동의 최소 횟수

 

 

 

첫 번째 시도

 

s = str(input())

cur = '0' # 현재 숫자
cnt = 0 # 뒤집기 횟수

for i in s:
    if i == cur:
        continue
    else:
        cnt += 1 # 뒤집기 횟수 + 1
        cur = i # 현재 숫자를 i로 변경

print(cnt//2) # 행동의 최소 횟수

-> 틀림

 

s = '0101'인 경우, cnt는 3이고, 행동의 최소 횟수는 2가 정답인데 위의 코드로는 1이 나옴

 

 

 

통과한 코드

 

s = str(input())

cur = '0' # 현재 숫자
cnt = 0 # 뒤집기 횟수

for i in s:
    if i == cur:
        continue
    else:
        cnt += 1 # 뒤집기 횟수 + 1
        cur = i # 현재 숫자를 i로 변경

# s가 1로 시작하는 경우, 뒤집기 횟수에서 1을 뺌 
if s[0] == '1':
    cnt -= 1 # 처음 시작 숫자를 0으로 해서 카운트 했기 때문에 1을 빼줘야 함

print((cnt+1)//2) # 행동의 최소 횟수

-> 최종 cnt에 1을 더한 값을 2로 나눈 몫이 행동의 최소 횟수

 

이때, 처음 시작 숫자를 0으로 해서 카운트했기 때문에 s가 1로 시작하는 경우는 cnt에서 1을 빼줘야 함 

 

 

 

다른 풀이

 

s = input()

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

print((cnt+1)//2)

-> 현재 숫자를 따로 변수로 선언하지 않고 인덱스로 현재 숫자와 다음 숫자가 다르면 뒤집기 횟수 + 1

 

 

 

 

 

참고)

 

https://codingpractices.tistory.com/72

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