[이코테][Chapter 11][문제] 3. 문자열 뒤집기

[문제설명]

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

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

하지만 처음부터 4번째, 5번째 문자열 00을 11로 뒤집으면 한 번만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어질 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력해라

[입력조건]

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만 보다 작다.

[출력조건]

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

---

다음과 같은 사고 과정을 거쳤다.

1. 000,111,...은 하나의 구간으로 두어서, 압축하여 0,1으로 표현할 수 있다.

2. 그러면 모든 문자열은 010101, 0101010 으로 표현될 수 있다.

3. 문자 하나를 뒤집을 경우, 구간은 2개가 줄어들게 된다. 이때, 하나의 문자는 왼쪽, 오른쪽 두 개의 숫자와 인접해 있으므로 최적의 방법이라는 것을 알 수 있다.

4. - 010101 형태는 행동의 최소 횟수는 (S의 길이)/2 이다.

- 0101010 형태는 행동의 최소 횟수는 (S의 길이-1)/2 이다.

이는, (S의 길이)//2 로 표현이 가능 하다.

 

#11-3. 문자열 뒤집기
#풀이
#경우의 수가 2가지가 있다.
#1. 10001010 처럼 1,0 구간 갯수가 같은 경우
#2. 10001011 처럼 1,0 구간 갯수가 다른 경우

#구간마다 튀어나오게 하는 경우
#횟수 : 구간의 개수

# 한 구간은 압축이 가능하므로,
# 01010101에서 가장 효율적인 방법을 찾으면 된다.
# 구간을 가장 빠르게 줄여나가는 방법을 택한다.
# 1. 구간을 튀어나오게 한다.
# 01010101에서
# 01110101으로.
# 이 경우 8개의 구간이 6개로 줄어들었다. 즉 2개가 줄어들었다.
# 그런데 한 구간이 붙어있는 곳의 구간은 "2개"이다.
# 따라서 이거보다 효율적인 방법은 없다.

#----------
#풀이 정리
#정리하다면, 다음의 두 가지를 고려해야 한다.
#1. 1,0 구간의 갯수가 같은가? 다른가?
#2. 111, 000처럼 연속된 숫자는 한 구간으로 친다.
#그러면 모든 숫자는 101010..., 10101 이 두 가지 경우만 생긴다.
#3. 한 구간을 뒤집는 형식으로 진행한다. 이러면 2개의 구간을 없앨 수 있다.
#한 구간이 붙어있는 구간은 2개이므로, 이게 가장 효율적인 방식이다.

#----------

#알고리즘
#1. 1,0 구간 갯수를 확인한다.
#같은 경우(짝수 개)의 행동 횟수: 구간 갯수 / 2
#다른 경우(홀수 개)의 행동 횟수: (구간 갯수 -1) / 2

#----------

#코드
#시작 구간
S = input()

#풀이 구간
import time
start_time = time.time()

section = 1
section_setting = S[0] #현재 구간은 0인가, 1인가? 를 설정하는 변수

for idx in range(1, len(S)): #구간 갯수 확인
    if(section_setting == S[idx]):
        continue
    else:
        section_setting == S[idx]
        section += 1

result = section // 2

#끝 구간
end_time = time.time()
print("행동의 최소 횟수 : ", result)
print("경과 시간: ", end_time - start_time)