Algorithm Problem with Python — 38day
문제 설명 📖
Given the head of a singly linked list, return true if it is a palindrome.
단일 링크된 목록의 head가 주어지면 참으로 반환하십시오.
제한사항
- The number of nodes in the list is in the range [1, 10⁵].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
입출력 예
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
문제 이해 🔑
인풋으로 날 마다의 주식의 가격이 주어집니다.
가격 중 저점에 사서 고점에 팔아 최대 이익을 찾는 문제입니다.
브루트 포스로 계산하면 이중 for문 사용하여 O(n²)으로 모든 경우의 수를 반복하여 마지막에 최대 이익을 산출할 수 있습니다.
하지만 타임아웃으로 풀리지 않습니다.
더 효율적인 풀이법으로는 저점과 현재 값과의 차이를 계산하는 것입니다.
인풋을 그래프로 x축에 인덱스, y축에 값을 적어 그려보면 직관적으로 답이 보입니다.
매일 값이 달라지기 때문에 현재 값을 가리키는 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격 차이를 계산하고, 만약 클 경우 최댓값을 계속 교체해나가는 형태로 O(n) 풀이가 가능합니다.
수도 코드 ✍️
풀이 1. 데크(Deque)를 이용한 최적화
- 데크 자료형을 선언합니다.
- 반복문을 통해 인풋 연결리스트를 끝까지 순회하여 데크 자료형에 연결리스트의 값을 하나씩 넣습니다.
- 데크 자료형이 존재할 때까지 순회합니다.
이 때, popleft()와 pop() 함수를 통해 맨 앞과 맨 뒤의 값을 비교합니다.
풀이 2. 러너(Runner)를 이용한 풀이
- 느린 러너와 빠른 러너 모두 head에서 시작합니다.
- 반복문을 통해 연결리스트가 끝날 때 까지 빠른 러너는 두 칸씩, 느린 러너는 한 칸씩 이동합니다.
- 한 칸씩 이동할 때 마다 느린 러너의 역순 연결 리스트를 만듭니다.
- 3번의 반복문이 끝나면 새로운 반복문을 통해 역순 연결 리스트의 값과 느린 연결 리스트의 값이 동일한지 비교합니다.
코드 작성 ⌨️
풀이 1. 데크를 이용한 최적화
# 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: 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풀이 2. 러너를 이용한 풀이
# 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: ListNode) -> bool:
rev = None
# 초깃값은 모두 head에서 시작
slow = fast = head
# print('slow', slow) ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}
# 러너를 이용해 역순 연결 리스트 구성
while fast and fast.next:
# 빠른 러너는 두 칸씩, 느린 러너는 한 칸씩 이동
fast = fast.next.next
# rev에 현재 slow, rev.next에 이전 rev를 넣어 역순 만듦, slow는 정방향으로 진행
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정리 😄
먼저 테크를 이용한 최적화 풀이는 리스트를 이용한 풀이를 데크를 통해 최적화한 방법입니다.
파이썬의 리스트는 pop() 함수를 통해 인덱스를 지정해서 비교가 가능하기 떄문에 이러한 풀이법이 있었습니다.
그러나 동적 배열로 구성된 리스트는 맨 앞의 아이템을 가져오기에 적합한 자료형이 아닙니다.
왜냐하면 첫 번째 값을 꺼내오면 모든 값이 한 칸씩 시프팅(shifting)되며, O(n)의 시간 복잡도가 발생하기 떄문입니다.
데크는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는데 시간 복잡도 O(1)에 실행되어 최적화가 가능했습니다.
그러나 연결 리스트 문제의 제대로 된 풀이법은 러너 기법을 활용하는 것입니다.
러너는 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법입니다.
한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있습니다.
빠른 러너가 연결 리스트의 끝에 도달하면, 느린 러너는 정확히 연결 리스트의 중간 지점을 가르키게 됩니다.
이 같은 방식으로 중간 위치를 찾아내면, 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러모로 활용할 수 있어 연결 리스트 문제에서는 반드시 쓰이는 기법입니다.
Reference
- 박상길, 『파이썬 알고리즘 인터뷰』, 책만 (2020), p201-212.
