[LeetCode] - 371. Sum of Two Integers
LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Sum of Two Integers " 문제입니다.
--> https://leetcode.com/problems/sum-of-two-integers/description/
문제 :
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1 :
Input : a = 1, b = 2
Output : 3
Example 2 :
Input : a = 2, b = 3
Output : 5
Constraints :
-1000 <= a, b <= 1000
이 문제는 주어진 두 정수 a와 b의 합을 +와 - 연산자를 사용하지 않고 반환해야 하는 코드를 써야 합니다. 되게 간단해 보이고, 접근 방식도 여러 가지 있다고 생각됩니다.
class Solution {
public int getSum(int a, int b) {
double N = (Math.pow(2, a)) * ( Math.pow(2, b));
int result = (int)(Math.log(N) / Math.log(2));
return result;
}
}
저는 보시다시피 수학적인 접근을 해봤습니다. 로그와 지수의 관계를 이용한 셈이죠. 2^a * 2^b = 2^(a+b) 로 볼 수 있습니다.
그리고, log_2(2^(a+b))는 결국 로그의 성질에 의해 a+b가 되기 때문에 문제를 바로 풀 수 있었습니다. 솔루션들을 봤을 때 보니까, 제가 제일 신선하게 푼 거 같더군요. 다른 사람들은 어떻게 했는지도 보시겠습니다.
시간 복잡도와 공간 복잡도 모두 O(1) 인 코드입니다.
class Solution {
public int getSum(int a, int b) {
int ans=0;
int carry=0;
while(b!=0){
ans=a^b;
carry=a&b;
carry=carry<<1;
a=ans;
b=carry;
}
return a;
}
}
// Mythili_Sakthivel 유저의 코드
이 코드는 두 정수 a와 b의 합을 비트 연산을 통해 구하는 방식으로 작성되었습니다. 이는 +와 - 연산자를 사용하지 않고도 덧셈을 수행할 수 있습니다. 비트 연산을 활용한 덧셈 방법은 다음과 같습니다:
- 비트 XOR (^) 연산 :
- a ^ b는 각 비트 위치에서 두 비트가 다를 때 1을 반환합니다. 이는 두 수의 합에서 캐리 비트를 제외한 결과를 나타냅니다.
- 예를 들어, a = 1 (0001), b = 2 (0010) 일 때, a ^ b = 3 (0011)이 됩니다.
- 비트 AND (&) 연산 후 왼쪽 쉬프트 (<<) :
- a & b는 각 비트 위치에서 두 비트가 모두 1일 때 1을 반환합니다. 이는 캐리 비트를 찾기 위한 연산입니다.
- 캐리 비트를 계산한 후, 이를 왼쪽으로 한 비트 이동시킵니다. 이는 실제로 캐리를 더하기 위해 다음 위치로 이동시키는 것입니다.
- 예를 들어, a = 1 (0001), b = 2 (0010)일 때, a & b = 0 (0000)이고, carry << 1 = 0 (0000)이 됩니다.
- 반복 :
- 위의 두 연산을 b가 0이 될 때까지 반복합니다. b가 0이 되면 더 이상 캐리가 없음을 의미합니다.
- 마지막에 a가 최종 결과를 갖게 됩니다.
시간과 공간 복잡도 모두 O(1)인 좋은 코드입니다.
