[2024] day 62. Leetcode 2864. Maximum Odd Binary Number

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 1일 (금)
Leetcode daily problem

2864. Maximum Odd Binary Number

https://leetcode.com/problems/maximum-odd-binary-number/description/?envType=daily-question&envId=2024-03-01

Problem

최소한 하나의 '1'을 포함하는 바이너리 문자열 's'가 주어질 때,
만들 수 있는 바이너리 문자열의 최대 홀수를 반환하도록 비트를 재배열한다.
반환하는 결과 문자열 앞에 0이 있을 수 있다.

Solution

array

일단 주어진 이진 문자열에서의 최대 '홀수' 이므로, 가장 마지막 문자열은 '1'로 끝나야 한다. 그리고 가장 최대를 찾기 위해서는 가장 앞단의 비트가 '1'로 시작하면 좋다.
해당 문자열을 위와 같이 구성하고 재정렬하기 위해서 주어진 문자열의 데이터타입을 리스트로 변경하고 핸들링 한다.

(1) 먼저 sorted 함수를 사용해 주어진 이진 문자열이 내림차순 정렬된 원소를 갖는 리스트를 만든다.
(2) 최대 수로 만든 수를 홀수로 만들기 위해서 (1)의 리스트 원소들을 끝에서부터 탐색해가면서 처음으로 찾은 홀수를 가장 마지막 문자열의 수와 swap 한다.
(3) 리스트 데이터타입을 join을 활용해 문자열로 다시 변환한다.

위의 과정을 통해서 가장 '최대' 이면서 '홀수'인 이진 문자열을 구할 수 있다.

Code

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        sorted_s = sorted(s, reverse=True)

        for i in range(len(s)-1, -1, -1):
            if sorted_s[i] == '1':
                sorted_s[i], sorted_s[-1] = sorted_s[-1], sorted_s[i]
                break

        return ''.join(sorted_s)               

Complexicity

시간 복잡도

주어진 문자열을 정렬할 때 O(nlogn),
문자열을 탐색할 때 최대 O(n)이 소요, 문자열을 다시 결합하여 반환하는데 O(n)이 소요된다.
최종 시간 복잡도는 O(nlogn)이다.

공간 복잡도

주어진 문자열을 내림차순해서 재 정렬하여 할당하므로 공간복잡도는 O(n)이다.