[LeetCode] 926. Flip String to Monotone Increasing

문제 출처: https://leetcode.com/problems/flip-string-to-monotone-increasing/

Flip String to Monotone Increasing - LeetCode

 

문제

만약 이진 문자열이 연속된 0(없을 수 있음) 이후에 연속된 1(없을 수 있음) 이 등장한다면 단조 증가이다.

 

이진 문자열 s 가 주어지고, s[i]를 0에서 1로 혹은 1에서 0으로 바꿀 수 있다.

 

단조 증가하는 s 를 만들기 위해 바꿔야 하는 문자의 수를 반환하라.

 

예제

Input: s = "00110"
Output: 1

Explanation: We flip the last digit to get 00111.

Input: s = "010110"
Output: 2

Explanation: We flip to get 011111, or alternatively 000111.

Input: s = "00011000"
Output: 2

Explanation: We flip to get 00000000.

 

풀이

최종적으로 만들고자 문자열의 형태에 대한 통찰을 얻기 위해서 예시로 나온 케이스를 살펴보자.

original => result
----------------------
00110	 => 00111
010110	 => 011111
010110	 => 000111
00011000 => 00000000

위 나열된 케이스를 살펴보면, 단조 증가 문자열은 어떤 한 지점을 기준으로 왼편은 0으로 설정되어 있고 오른편은 1로 설정되어 있다는 특징이 있다.

 

그래서 모든 지점을 기준으로 한 번씩 삼으면서 기준 왼쪽은 0, 오른쪽은 1인 상황을 만들기 위해서 몇 개의 문자를 바꿔야 하는지 체크하는 방식으로 문제를 풀고자 하였다. 

 

1. 최초 주어지는 문자에서 '0'이 몇개 있는지 카운트한다.
   • 모든 문자를 1로 만들기 위해서 몇 개의 문자가 바뀌어야 하는지 세기 위함
2. 모든 지점이 한 번씩 기준이 될 수 있도록 반복 시작(i = 0 ~ s.length-1)
   • 1을 0으로 바꾼 수 = 현재 지점(i) 포함 이전 인덱스에서의 1의 개수
   • 0을 1로 바꾼 수 = i 이후 인덱스에서의 0의 개수
                          = '(s에서의) 전체 0의 개수' - '(s에서의) 왼쪽 0의 개수'
                          = '(s에서의) 전체 0의 개수' - ('왼쪽의 길이' - '1에서 0으로 바뀐 수')

 

var minFlipsMonoIncr = function(s) {
    const zeroCount = s.split('').reduce((acc, b) => b == 0 ? acc + 1 : acc, 0);
    const N = s.length;
    
    let answer = zeroCount;
    
    let one2Zero = 0;
    for (let splitPoint = 0; splitPoint < N; splitPoint++) {
        if (s[splitPoint] == '1') { one2Zero += 1; }
        
        const leftZeroCount = splitPoint - one2Zero + 1;
        const zero2One = zeroCount - leftZeroCount;
        
        const totalFlipCount = one2Zero + zero2One;
        
        answer = Math.min(answer, totalFlipCount);
    }
    
    return answer;
};

 

Github: 926.js

GitHub - opwe37/Algorithm-Study