[Leetcode] 3228. Maximum Number of Operations to Move Ones to the End

문자열 s 가 주어진다. 그리고 (i + 1) < s.length 를 만족하는 모든 i 에 대해서 s[i] === 1 이고 s[i + 1] === 0 일 때 1을 가장 가까운 다른 1로 밀 수 있다(10001 -> 00011 이 가능하다). 이 때 해당 연산을 가장 많이 수행할 수 있는 횟수를 구하는 문제.

한마디로 모든 1을 오른쪽으로 보내야 하는데, 최대한 "비효율적"으로 보내는 방법을 물어보는 문제이다. 0은 여러개가 있어도 한번에 오른쪽으로 밀 수 있으므로 최대한 문자열의 왼쪽에 있는 1 부터 오른쪽으로 밀어야 연산을 많이 수행할 수 있다. 실제로 연산을 수행할 필요는 없고 문자열을 돌면서 0을 만날 때 마다 해당 0의 오른쪽이 벽이라면(1이거나 배열의 마지막이거나) 해당 0 의 왼쪽에 있는 모든 1을 여기까지 밀 수 있다는 의미이므로 지금까지 센 1의 갯수를 결과값에 더해주면 된다.

function maxOperations(s: string): number {
    let oneCount = 0
    let count = 0

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '1') {
            oneCount += 1
        } else {
            if (i + 1 === s.length || s[i + 1] === '1') {
                count += oneCount
            }
        }
    }

    return count
};