swift 리트코드 문제풀이 - leetcode 234 팰린드롬 연결 리스트 - ver.2

swift 리트코드 문제풀이 - leetcode 234 팰린드롬 연결 리스트 - ver.2

 

leetcode 234. Palindrome Linked List

 

이전 포스팅에서 연결 리스트를 이용한 팰린드롬 체크 문제를 while문과 배열을 이용해서 풀어보았다. (swift 리트코드 문제풀이 - leetcode 234 팰린드롬 연결 리스트)

 

이번 포스팅에서는 다른 방법을 이용해서 팰린드롬 연결 리스트 문제를 풀어볼려고 한다.

 

준비 코드는 이전 포스팅에서 설명을 했으므로, 이번 포스팅에서는 간단히 코드만 작성해놓는다...

아래와 같은 연결 리스트가 있고, 이 연결 리스트의 값이 팰린드롬인지 확인을 해보자. 즉 거꾸로해도 같은 값인지 체크를 하는 것이다.

let nodeFive = ListNode(1)
let nodeFour = ListNode(2,nodeFive)
let nodeThree = ListNode(3, nodeFour)
let nodeTwo = ListNode(2, nodeThree)
let head = ListNode(1,nodeTwo)

print("head : \( head ) \n" )
//head : 1 -> 2 -> 3 -> 2 -> 1

 

이번에는 러너(🏃‍♂️ )라는 개념을 이용해서 문제를 푸는데, 두 개의 러너(🏃 )를 사용한다.

(파이썬 알고리즘 인터뷰 라는 서적을 참고했는데, 파이썬 밖에 없어서 swift 버전으로 풀이했다. 개념은 동일하다고 보면됨)

 

첫번째 러너는 fast 러너로 연결 리스트의 노드를 2개씩 이동을 한다.

 

두번째 러너는 slow러너로 연결 리스트의 노드를 1개씩 이동을 한다.

 

여기서 문제! fast 러너가 연결 리스트의 마지막에 도착했을 때 slow 러너의 위치는 어디일까?

 

fast러너는 무조건 짝수 개씩(두칸) 이동을 하고, slow러너는 한 개씩 이동을 하므로 fast 러너가 끝에 도달 했을 때 slow러너는 연결 리스트의 중앙에 위치 하게 된다! 이게 러너 개념의 첫번째 핵심이다.

 

출처 파이썬 알고리즘 인터뷰 책

 

 

그리고 이어서 등장하는 rev 라는 변수가 있다.  이 변수의 초기 값은 nil 이다. 이 변수에는 slow 러너의 값을 역순으로 (!) 이어 붙여 줄것이다. 

slow 러너는 한칸씩 오른쪽으로 이동하므로 rev에 값을 역순으로 붙이게 되면

 

[1]rev : nil

[2]rev : 1 -> nil

[3]rev : 2 -> 1 -> nil

 

이런 식으로 붙게 된다. 여기까지가 rev 변수의 값을 만들어 주는 로직이다. 참고로 우리는 최종적으로 rev 값과, slow 값을 차례대로 비교해줄것이다.

 

func isPalindrome(_ head: ListNode?) -> Bool {
    
    /// slow가 우측으로 한칸씩 이동할때 slow의 값을 역순으로 연결 시킨다.
    /// 예) nil, 1 --> nil,  2-->1-->nil
    var rev:ListNode? = nil
    
    ///우측으로 한칸씩 이동한다.
    var slow = head
    
    ///우측으로 두칸씩 이동한다.
    var fast = head
    
    ///rev 만들기: slow 값을 rev에 역순으로 연결 시키는 작업
    ///fast가 두 칸씩 이동하면서 끝에 도달 했을 때 slow는 연결 리스트의 중앙에 위치 하게 된다.
    while fast?.next != nil{
        rev = ListNode(slow?.val ?? 0 , rev)
        slow = slow?.next
        fast = fast?.next?.next
        print("=== rev 만들기 ===")
        print("rev : \( rev! )" )
        print("slow : \( slow! )" )
        print("fast : \( fast! )" )
        print("")
    }
    
    return true
}

 

위 코드에서 while문 안의 print문을 출력해보면 아래와 같다. 출력문을 보면 rev와 slow의 값이 조금 비슷한것 처럼 보인다.

 

=== rev 만들기 ===
rev : 1
slow : 2 -> 3 -> 2 -> 1   
fast : 3 -> 2 -> 1  

=== rev 만들기 ===
rev : 2 -> 1 
slow : 3 -> 2 -> 1  
fast : 1

 

자 여기서 rev 가 2 -> 1 이고 slow가 3-> 2->1 이다. 

이때 입력 값이 홀수개 (1,2,3,2,1,) 이므로 입력 값이 홀 수개 일때는 정 가운데 3을 건너 뛰고 비교를 해야 한다.

 

즉, 입력 값이 홀수개일때 정중앙의 수는 빼고!

정중앙의 수 왼쪽 수들과 정중앙의 수 오른쪽 수들만 비교하면 된다는 말씀!

 

그럼 fast를 이용해서 fast가 nil이 아니면 slow를 오른쪽으로 한 칸 더 이동시켜주는 코드를 작성한다.

    //입력된 파라미터가 홀수인경우 slow를 중앙을 넘기기위해 우측으로 한칸 더 이동시킨다.
    if fast != nil {
        slow = slow?.next
    }
    print("slow : \( slow! )" )
    //slow : 2 -> 1

 

이제!  rev 가 2 -> 1 이고 slow가 2->1 이다. 뭔가 비슷? 똑같? 은것 같다. 이런식으로 비교하면 될것 같은 느낌 적인 느낌(?)이 든다!

 

이걸 보는 사람들도 이해가 됐겠지...? 이해가 안됐으면 나의 내공 부족...ㅜ

 

마지막으로 rev와 slow를 비교해주는 로직을 작성해보자.

 

rev 개수 만큼 돌면서 slow의 값과 rev의 값을 계속 비교를 한다. 하나라도 다른 값이 존재하면 false를 리턴해버린다.

    /// 위에서 만든 rev와 slow 값을 하나씩 비교해서 하나라도 틀리면 false를 리턴한다.
    while rev != nil{
        if rev?.val != slow?.val{
            return false
        }
        rev = rev?.next
        slow = slow?.next
    }

 

 

전체코드

xocde의 커맨드라인 프로젝트를 만들고 복붙해서 출력해보자!

import Foundation

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 isPalindrome(_ head: ListNode?) -> Bool {
    
    /// slow가 우측으로 한칸씩 이동할때 slow의 값을 역순으로 연결 시킨다.
    /// 예) nil, 1 --> nil,  2-->1-->nil
    var rev:ListNode? = nil
    
    ///우측으로 한칸씩 이동한다.
    var slow = head
    
    ///우측으로 두칸씩 이동한다.
    var fast = head
    
    ///rev 만들기: slow 값을 rev에 역순으로 연결 시키는 작업
    ///fast가 두 칸씩 이동하면서 끝에 도달 했을 때 slow는 연결 리스트의 중앙에 위치 하게 된다.
    while fast?.next != nil{
        rev = ListNode(slow?.val ?? 0 , rev)
        slow = slow?.next
        fast = fast?.next?.next
        print("=== rev 만들기 ===")
        print("rev : \( rev! )" )
        print("slow : \( slow! )" )
        print("fast : \( fast! )" )
        print("")
    }
    
    //입력된 파라미터가 홀수인경우 slow를 중앙을 넘기기위해 우측으로 한칸 더 이동시킨다.
    if fast != nil {
        slow = slow?.next
    }
    print("slow : \( slow! )" )

    /// 위에서 만든 rev와 slow 값을 하나씩 비교해서 하나라도 틀리면 false를 리턴한다.
    while rev != nil{
        if rev?.val != slow?.val{
            return false
        }
        rev = rev?.next
        slow = slow?.next
    }
    
    return true
}

//
let nodeFive = ListNode(1)
let nodeFour = ListNode(2,nodeFive)
let nodeThree = ListNode(3, nodeFour)
let nodeTwo = ListNode(2, nodeThree)
let head = ListNode(1,nodeTwo)

print("head : \( head ) \n" )
print("isPalindrome : \(isPalindrome(head) ))" )

 

결과

이전 포스팅에서 while문 과 배열을 이용한 로직보다 조금더 빠르다.

 

러너개념 참고

 

파이썬 알고리즘 인터뷰 책