연결 리스트가 팰린드롬 구조인지 판별하라.
1. 리스트 변환
from typing import List
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
q: List = []
if not head:
return True
node = head
# 리스트 변환
while node is not None:
q.append(node.val)
node = node.next
# 팰린드롬 판별
while len(q) > 1:
if q.pop(0) != q.pop():
return False
return True가장 간단한 방법은 리스트로 변환하여 pop()을 사용하는 것이다.
q.pop(0) != q.pop():로 팰린드롬인지 검사하고 빠져나올 수 있다.
2. 데크를 이용한 최적화
if q.pop(0) != q.pop():를 사용하여 간단하게 검사를 할 수 있지만 속도가 느린 것이 단점이다. 시간 복잡도가 O(n)이기 때문에 이를 더 빨리 검사하기 위해선 데크를 사용하면 된다.
이중 연결리스트니까 양쪽에서 추출해 O(1)로 시간을 줄일 수 있을 것이다.
리스트에서 데크로 바뀐 점은 1번과 거의 유사하다.
import collections
from typing import Deque
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 데크 자료형 선언
q: Deque = collections.deque()
if not head:
return True
node = head
while node is not None:
q.append(node.val)
node = node.next
while len(q) > 1:
if q.popleft() != q.pop():
return False
return True많이 바뀐 것도 없고 데크로만 바꾼 것인데 실행시간의 반토막이 났다.
근데 책에서는 리스트가 164밀리초, 데크가 72밀리초로 나오는데 나도 시간이 리스트와 비교해 반정도로 줄어들긴 했지만 실행시간이 왜 책이랑 많이 차이 나는지 잘 모르겠다.........;;
오늘 인터넷 상태가 안좋은가...
3.고를 이용한 데크 구현
전 문제들에서 고를 이용하여 다른 문제들을 풀어봤듯이 이번에도 고로 구현할 수 있는데 굳이 고로 구현하면 코드가 무척 길어진다.
// Go
// 데크(deque) 자료형을 Go로 바닥부터 구현한 풀이
const minCapacity = 16
type Deque struct {
buf []interface{}
head int
tail int
count int
minCap int
}
func (q *Deque) Len() int {
return q.count
}
func (q *Deque) PushBack(elem interface{}) {
q.growIfFull()
q.buf[q.tail] = elem
q.tail = q.next(q.tail)
q.count++
}
func (q *Deque) PopFront() interface{} {
if q.count <= 0 {
panic("deque: PopFront() called on empty queue")
}
ret := q.buf[q.head]
q.buf[q.head] = nil
q.head = q.next(q.head)
q.count--
return ret
}
func (q *Deque) PopBack() interface{} {
if q.count <= 0 {
panic("deque: PopBack() called on empty queue")
}
q.tail = q.prev(q.tail)
ret := q.buf[q.tail]
q.buf[q.tail] = nil
q.count--
return ret
}
func (q *Deque) prev(i int) int {
return (i - 1) & (len(q.buf) - 1)
}
func (q *Deque) next(i int) int {
return (i + 1) & (len(q.buf) - 1)
}
func (q *Deque) growIfFull() {
if len(q.buf) == 0 {
if q.minCap == 0 {
q.minCap = minCapacity
}
q.buf = make([]interface{}, q.minCap)
return
}
if q.count == len(q.buf) {
q.resize()
}
}
func (q *Deque) resize() {
newBuf := make([]interface{}, q.count<<1)
if q.tail > q.head {
copy(newBuf, q.buf[q.head:q.tail])
} else {
n := copy(newBuf, q.buf[q.head:])
copy(newBuf[n:], q.buf[:q.tail])
}
q.head = 0
q.tail = q.count
q.buf = newBuf
}
func isPalindrome(head *ListNode) bool {
var q Deque
if head == nil {
return true
}
node := head
for node != nil {
q.PushBack(node.Val)
node = node.Next
}
for q.Len() > 1 {
if q.PopFront() != q.PopBack() {
return false
}
}
return true
}이렇게 길어진 이유는 고에서는 데크 자료형을 지원하지 않는다. 외부라이브러릴 빌려와 사용 할 수 있지만 코딩테스트의 문제들을 풀어보기 위한 공부로 코딩테스트시에는 외부 라이브러리를 사용할 수 없다. 이렇게 직접 데크를 고로 구현하면 계산 시간은 매우 줄어들기는 한다.
근데 실용성은 떨어지는 것 같다.
4. 런너를 이용한 우아한 풀이
런너를 이용한 팰린드롬 검사는 빠른 러너, 느린 러너 두개의 런너를 이용하는 것이다.
hesd 1 2 3 2 1
1 fast --------> [rev = none]
2 slow ---> [rev=1->none]
3 fast --------> [rev=2->1->none]
slow --->
4 slow --->
런너의 진행 방식은 이렇게 빠른 런너가 2칸씩을 이동할 때 느린 런너는 1칸씩을 이동하며 연결리스트 rev를 만들어 간다.
중간에 도착한 느린 런너가 남은 경로를 이동하며 역순으로 만든 리트의 값과 똑같은지 검사하면서 간다.
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
rev = None
slow = fast = head
# 런너를 이용해 역순 연결 리스트 구성
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
if fast:
slow = slow.next
# 팰린드롬 여부 확인
while rev and rev.val == slow.val:
slow, rev = slow.next, rev.next
return not rev둘다 헤드에서 시작해서 빠른 런너는 2칸씩, 느린 런너는 1칸씩 이동하여 둘다 none이 될 때까지 이동하고 둘다 none이 되면 끝이 난다.
앞의 리스트와 데크의 방법보다 빨라진것을 확인 할 수 있다.
