[LeetCode] 2864. Maximum Odd Binary Number

https://leetcode.com/problems/maximum-odd-binary-number/description/

Maximum Odd Binary Number - LeetCode

Leetcode - Maximum Odd Binary Number

문제 유형 : 문자열처리, 비트마스킹, 그리디

문제 난이도 : Easy

 

문제

You are given a binary string s that contains at least one '1'.

You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.

Return a string representing the maximum odd binary number that can be created from the given combination.

Note that the resulting string can have leading zeros.

 

바이너리 문자열 s를 받는다. '1'이 적어도 하나 들어있다.

당신은 이 비트문자열을 가능한 가장 큰 홀수로 조합시켜야 한다.

 

풀이

순차적으로 문자열을 순회하면서 1의 개수를 찾는다.

1의 개수를 cnt개라고 했을 때, cnt-1개를 먼저 앞에 붙이고, 남은 0들을 뒤에 붙이고, 맨 뒤에 1을 붙이면 가장 큰 홀수를 만들 수 있다.

 

코드

C++

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int n = s.size();
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] == '1') cnt++;
        }

        string str = "";
        for(int i = 0; i < cnt-1; i++) {
            str += '1';
        }
        for(int i = 0; i < n-cnt; i++) {
            str += '0';
        }

        str += '1';
        return str;
    }
};