일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 데이콘
- hackerrank
- 프로그래머스
- 편스토랑
- Baekjoon
- leetcode
- ChatGPT
- Kaggle
- 편스토랑 우승상품
- 더현대서울 맛집
- 코로나19
- github
- gs25
- 자연어처리
- 백준
- 우분투
- PYTHON
- programmers
- SW Expert Academy
- Docker
- 맥북
- 프로그래머스 파이썬
- 금융문자분석경진대회
- ubuntu
- 파이썬
- dacon
- Git
- Real or Not? NLP with Disaster Tweets
- 캐치카페
- AI 경진대회
- Today
- Total
솜씨좋은장씨
[leetCode] 1073. Adding Two Negabinary Numbers (Python) (feat.ChatGPT) 본문
[leetCode] 1073. Adding Two Negabinary Numbers (Python) (feat.ChatGPT)
솜씨좋은장씨 2023. 3. 22. 15:24
코딩 1일 1문제! 오늘의 문제는 leetCode 의 Adding Two Negabinary Numbers 입니다.
👨🏻💻 문제 풀이 - 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]
더 최적화 된 코드를 알려줘! 라고 물으니 & 연산을 -> % 연산으로 // 연산을 -> >> 연산으로
변경한 코드로 알려주었습니다.
이 역시! 제가 푼 것과 큰 차이는 없었습니다.
이 문제를 풀어달라고 할때 놀랐던 점은 실제 문제를 풀었던 답변을 학습했는지
제출 칸에 적혀있는 기본 제출 폼까지 맞춰서 답변을 내주었다는 점이었습니다.
더 좋은 성능의 코드는! 좀 더 고민해봐야할 것 같습니다.
읽어주셔서 감사합니다.
'Programming > 코딩 1일 1문제' 카테고리의 다른 글
[leetCode] 2133. Check if Every Row and Column Contains All Numbers (Python) (feat.ChatGPT) (0) | 2023.03.25 |
---|---|
[leetCode] 2348. Number of Zero-Filled Subarrays (Python) (feat.ChatGPT) (0) | 2023.03.23 |
[leetCode] 1200. Minimum Absolute Difference (Python) (feat.ChatGPT) (0) | 2023.03.21 |
[BaekJoon] 17588번 : Missing Numbers (Python) (0) | 2023.03.20 |
[BaekJoon] 10480번 : Oddities (Python) (0) | 2023.03.17 |