swift 리트코드 문제풀이 - leetcode 24 페어의 노드 스왑

swift 리트코드 문제풀이 - leetcode 24 페어의 노드 스왑

 

24. Swap Nodes in Pairs

 

문제

연결 리스트를 입력받아 페어 단위로 스왑(Swap)하여라.

 

문제의 이해

문제 내용을 한번 살펴보면! 문제의 제시문 그대로다... 

인자로 연결 리스트가 주어지고, 우리는 우리가 구현할 함수 안에서 이 주어진 연결 리스트 안의 노드들의 값을 둘씩 짝을 지어서 서로 교환해서 리턴해주면 된다.

예를 들어 위의 그림에서 1,2,3,4 연결리스트가 들어왔으면 둘씩 짝을 지으면 (1,2) (3,4) 이렇게 짝을 지을 수 있다. 그리고 짝지어진 노드들을 서로 바꾸면 (2,1) (4,3) 이렇게 작성할 수 있겠다.

자 그럼..!

 

풀이 시나리오

코딩의 습작

[1] 일단 연결리스트의 모든 노드들을 스캔해야 되기 때문에 while문을 사용한다. 현재 node가 nil 이 아닐때까지 반복문을 돌면서 연결리스트 전체를 스캔한다.

 

[2] 홀수번째 노드와 짝수번째 노드 구분을 위한 index 변수를 선언한다. 우리는 홀 수번째 노드에서만 그 다음 노드와 값을 교환해 줄것이다. 왜냐면 1,2,3,4 이 연결리스트에서 첫 홀수 번째 노드를 돌때 뒤의 노드 값 2와 교환해주면 (2,1) 3 , 4 이렇게 된다. 여기까지 이해가 됐을까나..?

 

그럼 짝수번째의 노드는 (2,1) 3,4  여기서 1이다.

1의 위치, 즉 짝수번째에서도 다음 노드와 값을 교환 해버리면 2,(3,1) .. 이렇게 돼버린다. 결과적으로 페어 단위로 스왑이 일어나지 않게 되는 결과가 초래 되기 때문에 index를 선언해서 홀수 노드 일 때만 홀수 노드 위치에서 그 다음 노드의 값과 서로 교환해주고 짝수 노드의 우치에서는 아무런 작업도 해주지 않고 다음 노드로 건너뛰면된다.

 

[3] 그리고 while문을 들어가기위한 조건으로 주어진 인자가 nil 이 아니어야 하고, 최소 2개의 노드여야 while 문을 돌면서 페어 단위로 교환할 수 있다. 그래서 나중에 아래와 같은 로직을 함수 초입에 작성할 예정이다.

    /// 조건1: 연결리스트가 비었거나 하나일때 받은 인자 그대로 리턴
    if head == nil || head?.next == nil {
        return head
    }

 

[4] 또한 주어진 인자가 1,2,3,4 가 아니라 1,2,3 처럼 홀 수개 가 들어올 가능성도 염두해두어야 한다.

우리는 [2] 번에서 홀수 번째의 노드에서 다음 노드의 값과 교환을 시킬거라고 했는데 이런식으로 홀수개의 연결리스트가 들어오면 홀수번째 다음 노드가 없을 수도 있다. 이부분을 체크해주는 로직도 조건으로 작성해야 한다. 즉 홀수 번째 노드의 다음노드(next)가 nil 이면 현재 노드를 제일 마지막 노드에 연결시켜주면 된다. 아래와 같은 로직을 작성할 예정이다.

 

    /// 결과 연결리스트
    var resultList:ListNode?
    var index = 1
    var currrent = head

    while currrent != nil {
        
        /// 홀수 노드
        if (index % 2 != 0){
            
            /// 조건2: 홀수 노드인데 다음 노드가 없으면 (nil)이면
            if currrent?.next == nil {
                /// 현재 노드의 값을
                let nextNode = ListNode(currrent?.val ?? 0)
                /// 제일 끝 노드를 찾아서
                var cNode = resultList
                while cNode?.next != nil {
                    cNode = cNode?.next
                }
                /// 연결하기
                cNode?.next = nextNode

 

[5] 마지막으로 위의 조건들에 다 걸리지 않고 즉, 홀수번째 노드이고 다음 노드가 있을 경우에는 현재 노드의 값을 구하고, 다음 노드의 값을 구한 다음 각각의 값들로 새로운 Node를 생성한 다음 새로운 연결리스트에 연결시켜주면 끝이다.

 

그럼 위의 시나리오 대로 로직을 작성해 보자.

 

로직에는 상세하게 주석을 다 달아놓았다.

 

func swapPairs(_ head: ListNode?) -> ListNode? {
    

    /// 조건1: 연결리스트가 비었거나 하나일때 받은 인자 그대로 리턴
    if head == nil || head?.next == nil {
        return head
    }
    
    /// 결과 연결리스트
    var resultList:ListNode?
    var index = 1
    var currrent = head

    while currrent != nil {
        
        /// 홀수 노드
        if (index % 2 != 0){
            
            /// 조건2: 홀수 노드인데 다음 노드가 없으면 (nil)이면
            if currrent?.next == nil {
                /// 현재 노드의 값을
                let nextNode = ListNode(currrent?.val ?? 0)
                /// 제일 끝 노드를 찾아서
                var cNode = resultList
                while cNode?.next != nil {
                    cNode = cNode?.next
                }
                /// 연결하기
                cNode?.next = nextNode
            
            /// 홀수 인데 다음 노드가 있으면
            }else{
                    /// 현재값 , 다음값 구하기
                    let curVal = currrent?.val ?? 0
                    let nextVal = currrent?.next?.val ?? 0
                    
                    /// 값을 치환 하고 새로운 연결 리스트 만들어주는 로직
                    /// 결과 값을 담는 resultList 가 비어 있지 않으면
                    if resultList != nil {
                        
                        let nextNode = ListNode(curVal)
                        let curNode = ListNode(nextVal,nextNode)
                        
                        /// 제일 끝 노드를 찾아서
                        var cNode = resultList
                        while cNode?.next != nil {
                            cNode = cNode?.next
                        }
                        /// 연결시키기
                        cNode?.next = curNode
                        
                        print("resultList ::: \(resultList)")
                    
                    /// 결과 값이 비어 있으면
                    /// 즉, 제일 첫번째 한쌍의 노드 생성
                    }else{
                        let nextNode = ListNode(curVal)
                        let curNode = ListNode(nextVal,nextNode)
                        resultList = curNode
                    }
            }
        }
        
        print("resultList: \(resultList)")
        
        /// 연결 리스트 한칸 우측으로 이동
        currrent = currrent?.next
        index += 1
    }
    
    return resultList
}

 

위의 함수를 xcode나 playground에서 실행할려면 아래 함수도 같이 작성해주자. leetcode에는 위의 코드만 작성하면 된다. 만약 혼자서 코딩하고 테스트 해보고 싶다면 아래 함수도 추가해서 진행하면 된다. 참고로 제일아래 함수는 배열을 연결리스트로 만들어 주는 함수이다. 연결리스트를 일일이 하나씩 만들기 귀찮으니깐 let arr = [1,2,3,4] 배열을 만들고 let linkdedList = arrayToLinkedList(arr) 이런식으로 호출해서 사용하면 연결리스트가 만들어 진다. 이 연결리스트를 위에서 작성한 함수의 인자로 넣어주면 결과를 출력해 볼 수 있다.

 

/// 연결 리스트 노드
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
}

 

테스트

let swapPairsData = [1,2,3,4,5,6,7] 배열을 연결리스트로 만들고 위에서 만든 함수를 돌려보면 아래와 같은 값이 잘 출력됨을 확인 할 수 있다.

resultList: Optional(2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 7 )

 

 

leetcode 결과

 

 

https://leetcode.com/problems/swap-nodes-in-pairs/