Swift로 Leet Code 문제 풀기 - 21. Merge Two Sorted Lists (Easy)

아주 오랜만에 풀어보는 Leet Code~ 영어를 너무 오랜만에 봐서 머리가 띵하다.

21번 문제인 Merge Two Sortes Lists는 이미 오름차순 배열이 완료된 두개의 ListNode를 합쳐서 새로운 ListNode를 만들어내는 문제였다. 이것 또한 예시를 보면 바로 이해가 되었다.

 

출처: Leet Code

처음에는 '아 뭐야~~ 배열 두개 그냥 더해서 sort 한 번 돌리면 되겠네~~' 싶었는데 func의 인자를 보니 타입이 ListNode 형이라 1차 당황, 생겨먹은게 내가 자료구조 시간에 배웠던 linked list와 똑같아서 2차 당황...

 

재귀 함수가 무의식적으로 생각났는데 억지로 밀어 놓고 다른 방법으로 풀었다.

 

func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        guard let l1 = list1 else { return list2 }
        guard let l2 = list2 else { return list1 }
        
        var dummyNode: ListNode? = ListNode(-100)
        var list2Node: ListNode? = l2
        
        let headNode: ListNode? = dummyNode
        dummyNode?.next = l1
        
        
        while list2Node != nil {
            while dummyNode != nil {
                let next = dummyNode?.next
                
                if next == nil {
                    let newNode = ListNode(list2Node!.val, dummyNode?.next)
                    dummyNode?.next = newNode
                    break
                }
                
                if let next = dummyNode?.next, next.val >= list2Node!.val {
                    let newNode = ListNode(list2Node!.val, dummyNode?.next)
                    dummyNode?.next = newNode
                    break
                } else {
                    dummyNode = dummyNode?.next
                }
            }
            
            list2Node = list2Node?.next
        }
        
        return headNode?.next
    }

노드에 할당 가능한 숫자가 -99부터라는 점을 이용해 -99의 값을 가진 더미 노드를 하나 만들어 그 뒤에 list1을 붙였다. 그리고 return에 필요한 headNode를 저장해두었다. (headNode를 반환할 때는 더미 노드의 next를 반환하면 된다. 첫번째는 내가 만들어 넣은 -99 노드이므로)

 

그 후 list2의 노드를 dummyNode에 붙인 list1의 노드와 비교해 맞는 위치에 넣는 작업을 해주었다. (이것도 처음에는 dummyNode.val과 비교를 했더니 제대로 동작이 안돼서 dummyNode.next의 값과 미리 비교 후 넣어주었다.)

 

개발 할때는 강제 언래핑을 사용하지 않는 주의긴 하지만 알고리즘에서는 값이 있다는 걸 보장하는 경우엔 강제 언래핑을 사용하고 있다.

 

어찌저찌 풀긴 했는데 이제 재귀 함수에 익숙해질 때가 온 것 같다.. 공부좀 해야지.