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

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

 

leetcode 234. Palindrome Linked List

 

예제

 

이번에는 문제를 풀기전에 연결 리스트가 어떤 자료구조인지 알고 있어야 된다.. 연결 리스트의 장단점과 특징을 알고 있어야 되고, 연결 리스트를 코드로 간단하게라도 구현 할 수 있어야 한다. 아니면 최소 연결 리스트 코드를 보고 이해할 정도만되어도 될것 같다! 왜냐면 leetcode에서 연결 리스트의 노드에 해당하는 코드를 제공해 주기 때문이다.

 

아래 코드 처럼 연결 리스트의 각각의 Node에 해당하는 class 를 제공해준다. 그렇기 때문에 우리는 ListNode 클래스를 어떻게 사용해서 문제를 풀건지만 생각하면 된다.

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; }
}

 

먼저 작업을 하기 전에 내가 만든 Node 객체들이 연결 리스트로 잘 연결이 되어 있는지 쉽게 확인하기 위해서 위의 ListNode class를 아래와 같이 확장을 할 것이다. 이 코드는 print문으로 ListNode를 출력할때 현재 ListNode의 val를 출력하고 만약 현재 ListNode의 다음 노드인 next가 존재한다면 이어서 출력해주는 역할을 한다. 더 아래에서 예제를 보면 바로 확인 가능!

extension ListNode: CustomStringConvertible {
  public var description: String {
    guard let next = next else {
      return "\(val)"
    }
    return "\(val) -> " + String(describing: next) + " "
  }
}

 

자 준비는 끝났다.

 

그럼 leetcode의 예제대로 1,2,2,1을 연결 리스트로 만들어 보자.

총 4개의 Node 객체를 만들었다. 참고로 head는 -> nodeTwo를 가리키고 .... nodeTwo는 -> nodeThree를 가리키고...이런식으로 쭉 가다가 nodeFour는 -> nil을 가리키게 된다.

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

 

한번 head를 출력해보자. print로 출력했을 때 위의 extension 에 작성한 description 함수 내부가 작동이 된다. 출력은 아래와 같다.

1번 부터 단방향으로 잘 연결되어 나온것을 확인 할 수 있다.

print("head : \( head )" )

//출력 내용

head : 1 -> 2 -> 2 -> 1

 

이제 head를 leetcode에서 준 함수에 파라미터로 넣을 것이다. 아래에 빈칸을 채워서 head가 팰린드롬이면 true를 리턴하고 팰린드롬이 아니면 false를 리턴시키면 끝 -!

 

func isPalindrome(_ head: ListNode?) -> Bool {

	//채우기
    
    return 
}

 

그럼 핵심 로직을 생각해보자. 여러 방법이 있겠지만 바로 탁! 떠오른 방법은 

 

1. 연결리스트의 값을 배열에 while문을 돌면서 다 넣는다.

2.그 배열을 뒤집는다.

3.서로 비교한다. 

4.서로 같으면 true, 다르면 false

 

제일 만만한 방법인것 같다. 가장 직관적이고 원초적인?....?

 

위의 아이디어를 바탕으로 로직을 구성해보면 아래와 같다.

 

func isPalindrome(_ head: ListNode?) -> Bool {
    
    //[1].빈배열 생성
    var tempArray:[Int] = []
    
    //[2].연결리스트의 값을 배열에 삽입
    var currentNode = head
    while ((currentNode?.next) != nil) {
        tempArray.append(currentNode?.val ?? 0)
        currentNode = currentNode?.next
    }
    tempArray.append(currentNode?.val ?? 0)
    
    //[3].배열 뒤집기
    let reversedArry = tempArray.reversed()

    //[4].비교
    return tempArray.elementsEqual(reversedArry)
}

 

결과

 

 

https://leetcode.com/problems/palindrome-linked-list/