[2024] 3/1 Leetcode Daily Challenge 2864. Maximum Odd Binary Number

2864. Maximum Odd Binary Number

코드

풀이

step 1 : 가장 큰 수를 만들기 위해 QuickSort를 사용하여 '1'을 왼쪽부터 채워 넣음
ex) 10011 -> 11100, 000111 -> 111000

for i in range(len(s)):
	if s[i] == "1":
    s[left], s[i] = s[i], s[left]
    left += 1

step 2: 가장 끝 자리만 1이고 나머지는 다 짝수.(1 2 4 8 16 32 -> 2진수 계산)
그러므로 가장 끝 자리는 무조건 1이어야 홀수가 성립한다.
1 중에 가장 오른쪽에 있는 수(= 채워 넣은 1 중 가장 작은 자리 숫자)를 끝자리와 swap 해준다.

s[left - 1], s[len(s) - 1] = s[len(s) - 1], s[left - 1]

문법

• 문자열 -> 배열 변환

s = [ c for c in s ]

• 배열 -> 문자열 변환

''.join(s)

알고리즘

• QuickSort
  참고글

시간 복잡도

O(nlogn)