[leetCode] 1073. Adding Two Negabinary Numbers (Python) (feat.ChatGPT)

코딩 1일 1문제! 오늘의 문제는 leetCode 의 Adding Two Negabinary Numbers 입니다.

Adding Two Negabinary Numbers - LeetCode

👨🏻‍💻 문제 풀이 - SOMJANG

Negabinary 를 숫자로 바꾸어주는 함수와 숫자를 Negabinary 로 바꾸어주는 함수 2개를 만들어주었습니다.

2개의 함수를 활용하여 입력 받은 Negabinary 를 각각 숫자로 바꾸어 준 뒤 바꾸어 준 값을 더했습니다.

이 더한 값을 다시 Negabinary 로 바꾸어 주면 끝!

 

Negabinary -> 숫자 변환 함수는 아래와 같습니다.

def convertNegabinaryToInt(arr):
    arr_num = 0

    max_pow_num = len(arr) - 1

    for num in range(max_pow_num, -1, -1):
        if arr[max_pow_num - num]:
            arr_num += pow(-2, num)

    return arr_num

배열을 돌면서 1인 값만 -2의 (len(arr) - 1 - idx) 승 한 값을 모두 더해주었습니다.

 

숫자 -> Negabinary  변환 함수는 아래와 같습니다.

def convertIntToNegabinary(num):
    if num == 0:
        negabinary = [0]
    else:
        negabinary = []
        while num != 0:
            num, remainder = divmod(num, -2)

            if remainder < 0:
                num, remainder = num + 1, remainder + 2
            negabinary.append(remainder)

    return negabinary[::-1]

만약 숫자가 0이면 [0] 을 아닐 경우에는 숫자를 -2 로 나눈 몫과 나머지를 계산하고 

나머지가 0보다 크거나 같으면 그 값을 negabinary 리스트에 그대로 넣고

나머지가 0보다 작으면 +2 한 값을 negabinary 리스트에 넣었습니다.

 

마지막으로 이를 거꾸로 뒤집어주면 끝!

 

위의 두 함수를 활용하여 Solution 함수를 만들었습니다.

def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
    arr1_num = self.convertNegabinaryToInt(arr=arr1)
    arr2_num = self.convertNegabinaryToInt(arr=arr2)

    add_num = arr1_num + arr2_num

    return self.convertIntToNegabinary(num=add_num)

👨🏻‍💻 코드 ( Solution ) - SOMJANG

class Solution:
    @staticmethod
    def convertNegabinaryToInt(arr):
        arr_num = 0

        max_pow_num = len(arr) - 1

        for num in range(max_pow_num, -1, -1):
            if arr[max_pow_num - num]:
                arr_num += pow(-2, num)

        return arr_num

    @staticmethod
    def convertIntToNegabinary(num):
        if num == 0:
            negabinary = [0]
        else:
            negabinary = []
            while num != 0:
                num, remainder = divmod(num, -2)

                if remainder < 0:
                    num, remainder = num + 1, remainder + 2
                negabinary.append(remainder)

        return negabinary[::-1]

    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        arr1_num = self.convertNegabinaryToInt(arr=arr1)
        arr2_num = self.convertNegabinaryToInt(arr=arr2)

        add_num = arr1_num + arr2_num

        return self.convertIntToNegabinary(num=add_num)

실행 결과는 66ms 에 메모리 13.9MB 를 사용하는 것으로 나왔습니다.

 

이번에도 ChatGPT 는 어떻게 풀까? 더 좋은 결과를 내놓을까? 라는 궁금증을 가지고

ChatGPT 에게 풀어달라고 해보았습니다.

 

첫번째 시도는! 무한루프를 도는 코드여서 실패!

 

다시 풀어달라고 하니 아래와 같은 결과가 나왔습니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT 첫번째 풀이

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        i, j = len(arr1) - 1, len(arr2) - 1
        carry = 0
        res = []
        
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += arr1[i]
                i -= 1
                
            if j >= 0:
                carry += arr2[j]
                j -= 1
                
            res.append(carry & 1)
            carry = -(carry >> 1)
        
        while len(res) > 1 and res[-1] == 0:
            res.pop()
            
        return res[::-1]

ChatGPT 는 Negabinary 를 숫자로 바꾸지 않고 

그대로 각 자리수를 뒤에서부터 연산 하는 식으로 문제를 풀었습니다.

 

이렇게 풀었을때 실행결과도 제가 푼 것과 거의 차이가 없었습니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT 두번째 풀이 ( 최적화해줘 )

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        i, j = len(arr1) - 1, len(arr2) - 1
        carry = 0
        res = []
        
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += arr1[i]
                i -= 1
                
            if j >= 0:
                carry += arr2[j]
                j -= 1
                
            res.append(carry % 2)
            carry = -(carry // 2)
        
        while len(res) > 1 and res[-1] == 0:
            res.pop()
            
        return res[::-1]

 

더 최적화 된 코드를 알려줘! 라고 물으니 & 연산을 -> % 연산으로 // 연산을 -> >> 연산으로

변경한 코드로 알려주었습니다.

 

이 역시! 제가 푼 것과 큰 차이는 없었습니다.

 

이 문제를 풀어달라고 할때 놀랐던 점은 실제 문제를 풀었던 답변을 학습했는지

제출 칸에 적혀있는 기본 제출 폼까지 맞춰서 답변을 내주었다는 점이었습니다.

더 좋은 성능의 코드는! 좀 더 고민해봐야할 것 같습니다.

 

읽어주셔서 감사합니다.

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07