You are given a binary string binary consisting of only 0's or 1's. You can apply each of the following operations any number of times:

• Operation 1: If the number contains the substring "00", you can replace it with "10".
  • For example, "00010" -> "10010"
• Operation 2: If the number contains the substring "10", you can replace it with "01".
  • For example, "00010" -> "00001"

Return the maximum binary string you can obtain after any number of operations. Binary string x is greater than binary string y if x's decimal representation is greater than y's decimal representation.

Example 1:

Input: binary = "000110"
Output: "111011"
Explanation: A valid transformation sequence can be:
"000110" -> "000101"
"000101" -> "100101"
"100101" -> "110101"
"110101" -> "110011"
"110011" -> "111011"

Example 2:

Input: binary = "01"
Output: "01"
Explanation: "01" cannot be transformed any further.

Constraints:

• 1 <= binary.length <= 105
• binary consist of '0' and '1'.

[Greedy 알고리즘]

“순간에 최적의 선택을 하면, 결과적으로 전체의 최적의 선택이 된다!”

⇒ but NP-Hard 문제와 같이 모든 case를 대입하여도 풀 수 없는 문제에는 적용되지 않는다.

• 문자열을 차례대로 순회하며 ‘00’ 또는 ‘01’ 케이스가 나오면 변환할 때와 변화하지 않았을 때를 분기로 하여 ‘재귀 함수’를 돌리는 방법이 존재한다. (⇒ 케이스에 따라 매우 비효율적이 될 수 있는 가능성이 있다.)

  이 경우 이미 한 번 변경된 조합은 별도로 표시하여 무한 루프가 돌지 않도록 하는 Dynamic programming 방법이 병행되어야 한다.

• 하지만 동일한 greedy 알고리즘이라 하더라도, 아래와 같이 문제에서 주어진 규칙을 파악하고 나면 코드는 훨씬 효율적으로 변한다.