1. 문제 소개

3228. Maximum Number of Operations to Move Ones to the End

2. 나의 풀이

처음 생각한 풀이는 최대 연산을 구하는 것이라 1을 만날 때마다 1을 만난 횟수로 저장하고, 0을 만날 때 1을 만난 횟수를 결과에 저장하는 것으로 생각했다.
거의 정답이었지만 항상 0을 만날 때마다 결과에 저장하는 것이 아니라, 0을 만난 것을 on/off 스위치로 만들어 처음 0을 만날 때만 결과에 저장해 정답이 되었다.
시간복잡도는 $O(n)$이다.

class Solution:
    def maxOperations(self, s: str) -> int:
        ones = 0                 # 지금까지 등장한 1의 누적 개수
        zero = False             # 연속된 0 구간 중 처음 0인지 판별용
        ans = 0                  # 최대 연산 횟수 누적

        for n in s:              # 문자열을 왼쪽→오른쪽 순회
            if n == "1":
                ones += 1        # 1을 만나면 1의 누적 증가
                zero = False     # 새로운 1이 나왔으므로 0구간 초기화
            elif n == "0" and not zero:
                ans += ones      # 0을 처음 만날 때, 앞의 모든 1이 이 0을 앞질러야 함
                zero = True      # 같은 0 구간 내에서 중복 카운트 방지

        return ans               # 전체 가능한 최대 연산 횟수 반환

3. 다른 풀이

코드가 짧으면서 빠른 풀이를 하나 가져왔다.

class Solution:
    def maxOperations(self, s: str, res = 0, cnt = 0) -> int:

        # s.split('0') → 0을 기준으로 문자열을 나눈다.
        # 예: "1100101" → ['11', '', '1', '1']
        # 각 조각의 길이는 '연속된 1의 개수'를 의미함.
        for num in list(map(len, s.split('0'))):

            if num == 0:         # 0을 연속으로 만났다면 건너뛴다.
                continue

            cnt += num           # 현재 구간의 1 개수를 누적 (이전 구간의 1도 포함)
            res += cnt           # 누적된 1들이 이후의 0들을 넘어갈 때의 이동 횟수를 합산

        # 마지막 조각이 '1'으로 끝났다면 (즉, 문자열이 1로 끝남)
        # 마지막 구간에는 더 이상 0이 없어, 그 구간의 cnt만큼 과잉 더해져 있으므로 빼 준다.
        return res if num == 0 else res - cnt

4. 결론

한 번에 맞춰서 기분이 좋다.