[뒤집기] 1439번, 최소 뒤집기 구하기(2)

1. 문제 요약

/*
  * 문제 : 0과 1로 이뤄진 문자열에서 전부 0 또는 1로 바꾸는 상황
  * 조건
    - 0이나 1 둘중 하나로만 이뤄진 문자열로 변환
    - 뒤집기 연산도 0 또는 1 둘 중 하나로 수행됨
    - 문자열 길이는 100만이 최대
  * 출력 : 뒤집은 횟수 출력
*/

2. 풀이

(1) 0 또는 1로 이뤄진 집합 개수가 몇 개냐

순차 순회를 하면서, 연속적으로 나타나면 카운트 수를 늘리지 않음. "0->1, 1->0으로 변환된 지점 수를 셈"

case1. 원본 데이터

case2. 구현 하려는 개념

case3. 알고리즘 구현

(2) 변수 inver_last 역할

문자열 마지막 지점에 이전과 다른 값 하나가 나올 경우 카운트가 하나 덜 이뤄지는 문제점.

그래서 마지막 지점과 inverse 지점이 하나 더 있는 것으로 알려줌.

 

3. 다른 사람의 잘난 코드

(1) "달라지는 구간 개수/2 이 답이다."

첫 카운트 = 1부터 시작하면서 수를 세아려감.

case1. 첫 지점이 단일 구간

 

case2. 첫 지점이 연속된 1 구간

 

4. 코드

https://github.com/ukiKwon/algorithm-study/blob/master/%EB%92%A4%EC%A7%91%EA%B8%B0/1439.cpp