[LeetCode] 2938. Separate Black and White Balls

https://leetcode.com/problems/separate-black-and-white-balls/description/?envType=daily-question&envId=2024-10-15

leetcode - Separate Black and White Balls

문제 유형: 투 포인터, 그리디

문제 난이도 : Medium

 

문제

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.

 

테이블에 n개의 공이 있다.

각 공은 흑 또는 백색이다.

n길이의 문자열 s에 0-indexed로 비트문자열이 주어지는데, 1은 흑, 0은 백을 말한다.

당신은 두 인접한 공을 스왑할 수 있다.

흰공들이 왼쪽에, 검은공들이 오른쪽에 가기 위한 최소 스왑횟수를 구하시오.

 

풀이

풀이 1: 투포인터

투 포인터로 해결할 수 있다.

left를 0, right를 n-1 인덱스에 두고 시작한다.

 

left가 right보다 작은동안, 다음의 연산을 한다:

  left가 1일때까지 오른쪽으로 민다.

  right가 0일때까지 왼쪽으로 민다.

  s[left]와 s[right]의 요소를 바꾼다.

  right - left를 누적한다.

 

이는 누적되면, 버블정렬의 필요한 스왑개수가 된다.

과정도 버블정렬과 유사함을 알 수 있다.

왼쪽의 요소를 오른쪽 최대한 맨 끝으로 보낸 것이다.

 

풀이 2: 그리디

0의 이전의 1의개수를 누적할 ones를 만든다.

그뒤, 순차적으로 문자열을 순회한다.

만약 순회중 1을 만나면, ones를 1 누적한다.

0을 만나면, 앞의 1들과 교환되어야 한다는 의미로, ans에 ones를 누적한다.

 

 

코드

C++

풀이1

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long minimumSteps(string s) {
        int n = s.size();
        int left = 0;
        int right = n-1;
        long long ans = 0;

        while(left < right) {
            while(left < right && s[left] == '0') left++;
            while(left < right && s[right] == '1') right--;

            ans += right - left;
            swap(s[left], s[right]);
        }

        return ans;
    }
};

풀이2

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long minimumSteps(string s) {
        int n = s.size();
        int ones = 0;
        long long ans = 0;

        for(const auto &ch : s) {
            if(ch == '1') ones++;
            else ans += ones;
        }
        return ans;
    }
};