[LEET CODE] [python] 2938. Separate Black and White Balls

2938. Separate Black and White Balls

 

There are n balls on a table, each ball has a color black or white.

You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.

In each step, you can choose two adjacent balls and swap them.

Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

 

문제설명

0과 1로 이루어진 문자열이 주어진다. swap 은 인접한 두수만 할 수 있다. 최소 몇번의 swap 을 하면 정렬된 문자열을 얻을 수 있는가?

 

예시

input : 110 => output: 2

input : 101 => output: 1

 

풀이 1

문자열을 처음부터 순회하면서 현재 숫자가 1이고 그 다음 숫자가 0이면 swap 한다.

문자열이 완벽하게 정렬될때까지 이것을 반복한다.

=> 시간초과가 난다.

    def minimumSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 11010101 -> 00011111
        # 10101011 3
        # 01010111 3
        # 00101111 2
        # 00011111 1 -> 9


        li = []
        for ch in s:
            li.append(ch)

        flag = True
        cnt = 0
        while flag:
            flag = False
            for i in range(len(li)-1):
                if li[i] == '1' and li[i+1] == '0':
                    li[i], li[i+1] = li[i+1], li[i]
                    cnt += 1
                    flag = True
        return cnt

 

풀이 2

문자열에서 0을 만나게 되면 0을 만나기전까지의 1의 개수를 구해서 결과값에 합산한다. 

이렇게 하면 최초에 나온 0부터 앞으로 쭉 밀어 0번 인덱스로 보내고, 그 다음 나온 0은 1번인덱스로 옮기는 형식이라고 생각하면 된다. 이렇게하면 O(n) 의 시간복잡도로 이 문제를 풀 수 있다. 

class Solution(object):
    def minimumSteps(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 11010101 -> 00011111 // 2+3+4 => 9

        cnt1 = 0
        total = 0
        for ch in s:
            if ch == '0':
                total += cnt1
            else:
                cnt1+=1
        return total