swift 리트코드 문제풀이 - leetcode 2 두 수의 덧셈

swift 리트코드 문제풀이 - leetcode 2 두 수의 덧셈

 

2. Add Two Numbers

 

문제

역순으로 저장된 연결 리스트의 숫자를 더하라.

 

 

문제의 이해

인자로 두개의 연결리스트가 주어진다. 연결리스트 안의 값은 숫자타입이다.

예를 들어 [1,4] 연결 리스트 F와  [4,7,8] 연결 리스트 S가 주어졌다고 하면 연결리스트 안의 숫자들을 그대로 더해주면 된다.

 

위의 그림의 예제 처럼 연결리스트 안의 숫자를 다시 뒤집을 필요도 없다.

그냥 주어진 연결리스트 안의 노드 순서대로 숫자 하나씩 더해가면 된다.

 

1과 4를 더하면 = 5

4와 7을 더하면 = 11 

여기서 중요한게 10보다 같거나 크면 올림수를 처리해줘야 한다. 올림수는 carry라는 변수를 만들어서 저장하고 처리한다.

그럼 다시 4와 7을 더하면 = 1 이되고 carry = 1  이 된다.

마지막으로 S는 더 이상 노드가 없다. 그럼 0으로 할당하고 F는 8이 있으니 

0 + 8 + 1(carry) 하면 9 

이걸 연결 리스트로 만들면 5->1->9 이런식으로 출력이 된다.

 

풀이 시나리오

위에서 이해한 내용을 토대로 시나리오를 작성해 보면

[1] while 문을 이용해서 F 연결리스트와 S연결리스트가 둘중 하나라도 nil이 면 계속 반복문을 돌린다. 두 연결리스트의 길이가 같지 않을 수 있기 때문이 이렇게 작성을하고 두 연결리스트가 모두 nil 일 때만 반복문을 빠져 나오도록 한다.

 

[2] F의 값은 변수 a에 담고, S의 값은 변수 b에 담는다. 그리고 a와 b를 더한 수가 10보다 같거나 크면 carry 라는 변수에 할당해서 다음 노드의 계산에서 더해주도록 한다.

 

[3] 결과값으로 연결리스트로 만들어서 반환해 준다.

ㅈ

코드

위의 시나리오를 토대로 작성한 swift 코드 이다. 각 단계별로 주석을 달아 놓았다. 

위에서 간과한 부분이 하나 있는데, 연결리스트가 모두 종료되었을때 carray가 있을 수 있는 상황이다.

예를 들어 [9,9] 와 [9] 를 연산하면 while문을 총 2번 돈다. 하지만 연산의 결과 값은 108 즉 세자리 숫자가 나온다. cary가 있기 때문이다. 그래서 연결리스트의 개수가 최대 2개라서 두번만 돌면 10 이렇게 밖에 출력이 안된다는 점을 주의해야 한다. 그래서 제일 마지막에 연결 리스트가 모두 끝난상황에서 carry를 확인한다. 이 코드는 제일 아래 주석 [4] 번으로 표시해 놓았다.

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    
    var resultNode:ListNode?
    
    var carry = 0
    var aNum = 0
    var bNum = 0
    var resultNum = 0
    
    var first = l1
    var second = l2

    //[1] 반복 : 두 연결리스트 중 하나가 nil 이면 반복문 작동 - 둘다 nil 이면 정지
    while first != nil || second != nil {
        
        print("first val : \(first?.val ?? 0) , second val : \(second?.val ?? 0)")
        
        (first == nil) ? (aNum = 0) : (aNum = first?.val ?? 0)
        (second == nil) ? (bNum = 0) : (bNum = second?.val ?? 0)

        print("carry : \(carry) , aNum : \(aNum) , bNum : \(bNum) \n")
        
        //[2] 값 연산하기
        /// 10보다 크면 케리에 몫할당
        if (aNum + bNum + carry) >= 10 {
            // 나머지가 결과 값이 된다.
            resultNum = (aNum + bNum + carry) % 10
            // 몫은 케리값으로 할당 된다.
            carry = (aNum + bNum + carry) / 10
            
        }else {
            resultNum = aNum + bNum + carry
            carry = 0
        }
        
        
        ///[3] 연결리스트 만들기
        if resultNode == nil{
            resultNode = ListNode(resultNum)
        }else{
            //제일 끝에 연결 시켜야함
            var curNode = resultNode
            while curNode?.next != nil{
                curNode = curNode?.next
            }
            curNode?.next = ListNode(resultNum)
        }
        
        first = first?.next
        second = second?.next
        
        
        ///[4] 연결리스트가 모두 종료되었지만 carry 값이 있을경우
        /// 연결 리스트의 끝에 도달했지만 carry값이 0보다 클경우 Node를 하나 더 만들어서 붙여준다.
        if first == nil && second == nil && carry != 0{
            //제일 끝에 연결 시켜야함
            var curNode = resultNode
            while curNode?.next != nil{
                curNode = curNode?.next
            }
            curNode?.next = ListNode(carry)
            carry = 0
        }
    }
    
    print("resultNode : \(resultNode)")
    
    return resultNode
}

 

테스트

아래와 같이 정상적으로 출력되는 것을 확인 할 수 있다. arrayToLinkedList 함수는 테스트 할때 용이하도록 배열을 연결리스트로 바꾸어 주는 함수이다. 직접 xcode에서 테스트 해볼려면 아래 테스트용 함수들이라는 부분의 코드를 붙여 넣으면 된다.

var f = [9,9,9,9,9,9,9]
var s = [9,9,9,9]
addTwoNumbers(arrayToLinkedList(arr:f), arrayToLinkedList(arr: s))

//출력 결과 resultNode : Optional(8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1)

 

테스트용 함수들

/// 연결 리스트 노드
public class ListNode {
public var val: Int
public var next: ListNode?
public init() { self.val = 0; self.next = nil; }
public init(_ val: Int) { self.val = val; self.next = nil; }
public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
   
}

/// 노드 연결 상태 출력
extension ListNode:CustomStringConvertible{
   public var description: String{
       guard let next = next else {
           return "\(val)"
       }
       return "\(val) -> " + String(describing: next) + " "
   }
}

///배열을 연결 리스트로 만들기
func arrayToLinkedList(arr:[Int]) -> ListNode? {
    
    var nextResultNode:ListNode?
    var idx = arr.count - 1
        
    while(idx >= 0){
        
        let char = arr[idx]
        let num =  Int(String(char)) ?? 0
        
        ///꼬리 노드
        if idx == arr.count - 1 {
            nextResultNode = ListNode(num)
        }else{
            let node = ListNode(num , nextResultNode)
            nextResultNode = node
        }
        idx -= 1
    }
    return nextResultNode
}

 

leetcode 결과

 

 

https://leetcode.com/problems/add-two-numbers/