LeetCode 알고리즘 Sum of Two Integers

안녕하세요 오늘은 371 문제를 풀어보겠습니다.
난이도는 Medium, Acceptance는 50.6%입니다.

 

문제를 봅시다아

두 정수 a,b가 주어지면 두 정수를 더한 값을 리턴해라.
단 +,- 연산자는 쓰지마

Example 1번을 살펴보면 1, 2를 더한 값인 3을 리턴해주고
Example 2번을 살펴보면 2,3을 더한 값인 5를 리턴해줍니다.

---

마음으로는 advanced(by: ) 함수 써서 끝낼 텐데^^,,

 

func getSum(_ a: Int, _ b: Int) -> Int {
    return a.advanced(by: b)
}

조금 남은 양심이 말리네요.

 

근데 21년 5월 30일에 그렇게 풀었음ㅋ
심지어 22년 9월 15일에도 동일하게 advanced(by: )로 풀었음ㅋ

이 정도면 잔머리 대마왕이다.

 

advanced(by: )는 특정 값 기준 offset된 거리를 반환해주기 때문에
advanced(by: )쓰면 쉽게 해결되는데^^,,,

근데 애플 공식문서에 보면
If you're working directly with numeric values, use the addition operator instead of this method
라고 적혀있긴 함ㅋㅋ

---

그래서 다른 방법

 

2진수 바이너리
비트 연산자를 활용해서 문제를 해결해보려 합니다.
(근데 이거 정보처리기사 단골 문제 아닌교)

func getSum(_ a: Int, _ b: Int) -> Int {
    var a = a 
    var b = b 
    
    while b != 0 {
        let carry = (a & b) << 1 
        a = a ^ b 
        b = carry
    } 
    
    return a
}

b가 0이 아닐 때까지 계속 돌도록 while 조건문을 설정해주고
carry에는 (a & b) << 1을 넣어줍니다.
여기서 &(AND)는 두 비트가 같은 값인 경우 1 다른 경우 0으로 변환하죠.
여기서 << 1은 시프트 연산자이고 이를 활용해 비트를 왼쪽으로 밀어줍니다.

a에는 a ^ b를 넣어주고 
여기서 ^(XOR)는 두 비트가 다른 경우에 1 같은 경우에 0을 가지죠.

마지막으로 b에는 carry를 넣어주면 됩니다.

 

즉
XOR는 두 비트가 다르면 1 같으면 0이고
AND는 두 비트가 모두 1이면 1 아니면 0이라
XOR을 통해서 올림수가 발생하는 1 + 1을 제외한 덧셈이 가능하고
AND를 통해 올림수가 발생해서 왼쪽의 비트를 + 1 해줘야 하는 상황에
<< 왼쪽 시프트 연산을 해줘 해결 가능합니다

---

헷갈리니까 예제로 ㄱㄱ

예제 1번
a가 1이고 b가 2입니다.

carry를 구하는 (a & b) << 1에서
괄호 안 (a & b)을 먼저 보겠습니다.
(a & b)는 비트 연산자 AND를 사용한 것이니
 두 비트가 같은 값인 경우 1 다른 경우 0으로 변환하죠.
그래서 나온 값 00000000
다음 비트 시프트 연산자를 활용해 비트를 왼쪽으로 밀어줍니다.
하지만 0 이니까 << 1 시프팅을 해도 0이겠죠?
carry는 00000000 즉 0이 됩니다.

다음 a에는 a ^ b를 넣어줍니다.
^는 비트 연산자 XOR이니 두 비트가 다른 경우에 1 같은 경우에 0을 가지죠.
그래서 나온 값 00000011
a는 00000011 즉 3이 됩니다.

다음 b 에는 carry 값을 넣어줍니다.
위에서 구한 carry는 00000000이라 b는 00000000 즉 0이 됩니다.

다음 while문을 돌려하는데 b가 0이니 조건에 맞지 않아
그대로 return 됩니다.

 

예제 2번
a가 2고 b가 3입니다.

carry를 구하는 (a & b) << 1에서
괄호 안 (a & b)을 먼저 보겠습니다.
(a & b)는 비트 연산자 AND를 사용한 것이니
 두 비트가 같은 값인 경우 1 다른 경우 0으로 변환하죠.
그래서 나온 값 00000000
다음 비트 시프트 연산자를 활용해 비트를 왼쪽으로 밀어줍니다.
하지만 0 이니까 << 1 시프팅을 해도 0이겠죠?
carry는 00000000 즉 0이 됩니다

다음 a에는 a ^ b를 넣어줍니다.
^는 비트 연산자 XOR이니 두 비트가 다른 경우에 1 같은 경우에 0을 가지죠.
그래서 나온 값 00000101
a는 00000101 즉 5가 됩니다.

다음 b 에는 carry 값을 넣어줍니다.
위에서 구한 carry는 00000100이라 b는 00000100 즉 4가 됩니다.

다음 while문을 돌려하는데 b가 4니 조건에 맞아
다시 동일한 로직이 실행됩니다.

이제는 a가 1이고 b가 4입니다.

carry를 구하는 (a & b) << 1에서
괄호 안 (a & b)을 먼저 보겠습니다.
(a & b)는 비트 연산자 AND를 사용한 것이니
 두 비트가 같은 값인 경우 1 다른 경우 0으로 변환하죠.
그래서 나온 값 00000010
다음 비트 시프트 연산자를 활용해 비트를 왼쪽으로 밀어줍니다.
carry는 00000100 즉 4가 됩니다.

다음 a에는 a ^ b를 넣어줍니다.
^는 비트 연산자 XOR이니 두 비트가 다른 경우에 1 같은 경우에 0을 가지죠.
그래서 나온 값 00000001
a는 00000001 즉 1이 됩니다.

다음 b 에는 carry 값을 넣어줍니다.
위에서 구한 carry는 00000000이라 b는 00000000 즉 0이 됩니다.

다음 while문을 돌려하는데 b가 0이니 조건에 맞지 않아
그대로 return 됩니다.

---

 이렇게 제출하면 아래와 같은 결과가 나오네요.

https://leetcode.com/problems/sum-of-two-integers/
https://developer.apple.com/documentation/swift/int/advanced(by:)