Python/코딩 문제

[리트코드] 234. Palindrome Linked List

green_ne 2022. 1. 12. 19:07

# 문제 설명

주어진 연결리스트가 팰린드롬(Palindrome) 구조인지 판별하시오.

 

팰린드롬(Palindrome)이란 회문을 말한다.

예를 들어 "tenet", "level", "Madam, I'm Adam" 과 같이 역순으로 읽어도 같은 말이 되는 말을 말한다.

 

# 입출력 예시

입력 출력
1 -> 2 -> 2 -> 1 true
1 -> 2 false

 

# 코드 풀이 1. py-list 자료구조 활용

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
    	
        # 예외처리: head가 None이라면
        if not head:
            return True
        
        stack = []
        while head is not None: # 값이 아닌 클래스라면 is연산자
       	    stack.append(head.val)
            head = head.next
        
        # 주의! 홀수길이의 stack일 때, 중간값 연산
        # 방법 1. list 인덱싱
        for i in range((len(stack)+1)//2):
            if stack[i] != stack[-(i+1)]:
                return False
        return True
        
        # 방법 2. list 삭제 
        while len(stack) > 1:
            if stack.pop(0) != stack.pop():
                return False
        return True

 

먼저 연결리스트를 모두 읽어 List에 저장한다. 양쪽 끝의 문자를 하나씩 비교하면서 팰린드롬이 맞는지 확인한다.

방법 1은 인덱싱(indexing)으로 구현한 것이고, 방법 2는 pop() 삭제로 구현한 방법이다.

 

 

 

# 코드 풀이 2. py-deque 자료구조 활용

from collections import deque

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
    	
        if not head: # 예외처리: head가 None이라면
            return True
        
        q = deque()
        while head is not None: # 값이 아닌 클래스라면 is연산자
            q.append(head.val)
            head = head.next
        
        while len(q) > 1:
            if q.popleft() != q.pop():
                return False
            return True

 

팰린드롬을 판별하기 위해서 양쪽 끝의 문자를 확인해야 한다. Deque는 양쪽 끝에서 삽입/삭제가 가능한 자료구조로, List와 달리 삽입/삭제 연산을 하는 데 O(1)의 시간복잡도를 소요한다.

 

 

# 코드 풀이 3. Runner 기법 활용

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow = fast = head
        
        while fast and fast.next: # 런너로 역순 연결리스트 구성
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        
        # 팰린드롬 여부 확인
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev

 

앞선 풀이 1, 2의 경우에 입력이 연결리스트로 주어지기 때문에 1번 모든 값을 읽고, 문제 조건에 맞는지 확인하기 위해 다시 절반을 읽어야 한다. 이와 같은 연결리스트 문제를 풀 때, 효과적인 기법인 런너(Runner) 기법이 있다.

 

런너(Runner) 기법은 연결리스트를 순회하면서, 2개의 포인터를 동시에 사용하는 방법이다.

 - 빠른 런너(Fast Runner) : 대개 2칸씩 포인터를 건너뛰고,

 - 느린 런너(Slow Runner) : 1칸씩 포인트를 이동한다.

 

위와 같이 순회를 진행하면, 빠른 런너가 끝에 도달했을 때 느린 런너는 중간 위치에 도달하게 된다.

따라서 여기서 부터 원하는 연산을 진행하는 방법이다.

 

 

# 핵심 포인트

- 홀수 길이의 연결리스트가 주어질 때, 중간값을 연산하는 데 주의가 필요하다.

 

- 팰린드롬을 판별하기 위해서는 양쪽의 문자가 같은지 확인해야 한다. 따라서 이 연산을 처리하기 위한 효과적인 자료구조나 알고리즘 선정이 중요하다.

예를 들어, List 자료구조의 삽입/삭제 연산을 수행하는데 O(n)의 시간복잡도가 소요된다.

하지만 Deque 자료구조를 활용하면 O(1)에 삽입/삭제 연산을 수행할 수 있다.

 

- 연결리스트를 순회하는 문제를 풀 때, 런너(Runner) 기법을 사용하면 효과적으로 풀 수 있다.

 

 

 

 

다음은 Python 자료구조 연산들의 시간복잡도를 정리한 글이다.

https://wiki.python.org/moin/TimeComplexity

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

반응형