Python Algorithm 1. 스택

ADT -> 추상적 데이터 타입
스택 ?
배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조입니다.
스택은 배열 인덱스 접근이 제한되어 -> 후입선출(LIFO)의 구조를 가지고 있습니다.
스택은 나중에 들어간 데이터가 가장 먼저 나옵니다.

push : 스택의 맨 위(끝)에 항목을 삽입
pop : 스택의 맨끝을 반환하는 동시에 삭제
top/peek : 스택 맨 끝의 항목을 조회
empty : 스택이 비어있는지 확인합니다.
size : 스택의 크기를 확인합니다.

class Stack(object):
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return not bool(self.items)
    
    def pop(self):
        value = self.items.pop()
        if value is not None:
            return value
        else:
            print("Stack is Empty")
    def size(self):
        return len(self.items)
    
    def push(self, value):
        self.items.append(value)
    
    def peek(self):
        if self.items:
            return self.items[-1]
        else:
            print("스택이 비었습니다.")
    
    def __repr__(self):
        return repr(self.items)
    
if __name__ == "__main__":
    stack = Stack()
    print("스택이 비었음 ? {0}".format(stack.isEmpty()))
    print("스택에 값을 추가합니다.")
    for i in range(10):
        stack.push(i)
    print("스택의 크기는 ? {0}".format(stack.size()))
    print("peek : {0}".format(stack.peek()))
    print("pop : {0}".format(stack.pop()))
    print("peek : {0}".format(stack.peek()))
    print(stack)

# 실제 쓰이는 방법

class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer
        

#스택구현
class Stack(object):
    def __init__(self):
        # 헤드를 None으로 기존에 아무것도 연결이 되면 안되기 때문에 None으로 초기화 해준다.
        self.head = None
        self.count = 0

    def isEmpty(self):
        return not bool(self.head)
        # 여기 중요!
    def push(self, item):
  			#item은 value, self.head self.head는 노드의 형태를 가지고 있기 때문에 일반적인 상태는 아니다.
        self.head = Node(item, self.head)
        self.count += 1
            
    def pop(self):

            # 팝은 self.count가 1보다 무조건 커야되고
            # self.head가 둘다 있어야 작동합니다.
        if self.count > 0 and self.head:

            node = self.head

            # self.head에 지금 새로 선언한 node.pointer를 연결해줌으로써 헤드를 반환하고 그 전에 있던 노드 객체를 가져와서 헤드에 넣어준다.

            self.head = node.pointer
            self.count -= 1
            return node.value
        else:
            print("스택이 비었음")
        

    def peek(self):
        if self.count > 0 and self.head:
            return self.head.value
        else:
            print("스택이 비었음")
            
    def size(self):
        return self.count
    

    # node형태로 출력이 안되어 안에 있는 node값만 찾는 매서드
    def _printList(self):
        node = self.head
        while node:
            print(node.value, end=" ")
            node = node.pointer
        print()
        
if __name__ == "__main__":
    stack = Stack()
    print("스택이 비었음 ? {0}".format(stack.isEmpty()))
    print("스택에 값을 추가합니다.")
    for i in range(10):
        stack.push(i)
    print("스택의 크기는 ? {0}".format(stack.size()))
    print("peek : {0}".format(stack.peek()))
    print("pop : {0}".format(stack.pop()))
    print("peek : {0}".format(stack.peek()))
    stack._printList()                

#큐

# 큐는 스택과는 다르게 들어온 순서대로 접근이 가능합니다.
# 먼저 들어온 데이터가 먼저 나가는 선입선출 구조(FIFO)입니다.
# 큐는 배열 인덱스 접근이 제한되서 잘 사용해야합니다.
# 줄 선 순서대로 차근차근 들어갔다가 차근차근 나오는 순서

# 큐의 용어
# enqueue : 큐의 뒤쪽에 항목을 삽입한다.
# dequeue : 큐 앞쪽의 항목을 반환하고, 제거한다.
# peek / front : 큐의앞쪽 항목을 조회한다.
# empty : 큐가 비었는지 확인한다.
# size : 큐의 크기를 확인한다.

class Queue(object):
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return not bool(self.items)
    
    def enqueue(self, item):
        self.items.insert(0, item)
        
    def dequeue(self):
        value = self.items.pop()
        if value is not None:
            return value
        else:
            print("큐가 비었습니다.")
            
    def size(self):
        return len(self.items)
    
    def peek(self):
        if self.items:
            return self.items[-1]
        else:
            print("큐가 비었습니다.")
            
    def __repr__(self):
        return repr(self.items)
    # 주석 달라고요 ㅋㅋ
    # 이해한대로
if __name__ == "__main__":
    queue = Queue()
    print("큐가 비었음 ? {0}".format(queue.isEmpty()))
    print("큐에 0 ~ 9까지 추가합니다.")
    for i in range(10):
        queue.enqueue(i)
        
    print("큐의 크기 : {0}".format(queue.size()))
    print("peek : {0}".format(queue.peek()))
    print("dequeue : {0}".format(queue.dequeue()))
    print("peek : {0}".format(queue.peek()))
    print(queue)

# 노드 컨테이너 -> 스택
# 노드 컨터에너 -> 큐
class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer
        
class LinkedQueue(object):
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0
        
    def isEmpty(self):
        return not bool(self.head)
    
    def dequeue(self):
        if self.head:
            value = self.head.value
            self.head = self.head.pointer
            self.count -= 1
            return value
        else:
            print("큐가 비었습니다.")
            
    def enqueue(self, value):
        node = Node(value)
        if not self.head:
            self.head = node
            self.tail = node
        else:
            if self.tail:
                self.tail.pointer = node
            self.tail = node
        self.count += 1
        
    def size(self):
        return self.count
    
    def peek(self):
        return self.head.value
    
    def _print(self):
        node = self.head
        while node:
            print(node.value, end=" ")
            node = node.pointer
        print()
if __name__ == "__main__":
    queue = LinkedQueue()
    print("큐가 비었음 ? {0}".format(queue.isEmpty()))
    print("큐에 0 ~ 9까지 추가합니다.")
    for i in range(10):
        queue.enqueue(i)
    queue._print()   
    print("큐의 크기 : {0}".format(queue.size()))
    print("peek : {0}".format(queue.peek()))
    print("dequeue : {0}".format(queue.dequeue()))
    print("peek : {0}".format(queue.peek()))
    queue._print()
    for i in range(11, 20):
        queue.enqueue(i)
    
    queue._print()   

# 덱
# 스택과 큐의 집합체
# 양쪽 끝에서 항목을 조회, 삽입, 삭제가 가능합니다.

class Deque(Queue):
    def enqueue_back(self, item):
        self.items.append(item)
        
    def dequeue_front(self):
        value = self.items.pop(0)
        if value is not None:
            return value
        else:
            print("데크이 비었습니다.")
            
if __name__ == "__main__":
    deque = Deque()
    print("덱이 비었음 ? {0}".format(deque.isEmpty()))
    print("덱에 숫자를 추가합니다.")
    for i in range(10):
        deque.enqueue(i)
    print("데크 : {0}".format(deque))
    print("peek : {0}".format(deque.peek()))
    print("dequeue : {0}".format(deque.dequeue()))
    print("데크 : {0}".format(deque))
    print("enqueue_back : {0}".format(deque.enqueue_back(50)))
    print("데크 : {0}".format(deque))
    print("dequeue_front : {0}".format(deque.dequeue_front()))
    print("데크 : {0}".format(deque))
    

from collections import deque
q = deque(["엔젤", "카키", "코루"])
q
q.append("마일스")
q
# 왼쪽의 값을 빼포 싶다.
q.popleft()
q
# 오른쪽의 값 빼고 싶다./
q.pop()
q
# 왼쪽에 다시 추가 하고싶다.
q.appendleft('엔젤')
q
# rotate(n) : n의 길이만큼  양수면 오른쪽으로 가거나  음수면 왼쪽으로 갑니다.
q.rotate(2)
q
q.rotate(-2)
q

# collections 안의 Deque은 이중 연결 리스트 형식으로 되어져 있기 때문에
# 이러한 현상이 일어난다.

>>> deque(['엔젤', '카키', '코루'])

# 우선 순위 힙, 큐

# 우선순위 큐
# 일반 스택과 큐와 비슷한 추사아 데이터 타입
# 각 항목마다 연관된 우선순위가 있습니다.
# 두 항목의 우선순위가 같으면 큐의 순서를 따릅니다.
# 우선 순위 큐는 힙을 사용해서 구현합니다.
# 힙
# 일반적으로 리스트에서 가장 작은 요소에 반복적으로 접근하는 프로그램에
# 유용하게 사용됩니다.
# 최소 힙을 사용하면 가장 작은 요소를 처리하는 시간복잡도도 빠른편입니다.

# heapq 모듈
# 효율적으로 시퀸스를 힙으로 유지하면서
# 항목을 삽입하고 삭제하는 함수를 제공합니다.
import heapq
list1 = [1,3,8,9]
heapq.heapify(list1)
list1

>>> [1, 3, 8, 9]

# 항목에 힙을 삽입하는 방법
# heapq.heappush(heap, item)

h = []
heapq.heappush(h, (1, "Food"))
heapq.heappush(h, (2, "I'm"))
heapq.heappush(h, (3, "Very"))
heapq.heappush(h, (4, "Good"))
print(h)

>>>[(1, 'Food'), (2, "I'm"), (3, 'Very'), (4, 'Good')]

# 힙에서 가장 작은 요소를 제거하고 반환해줍니다.
# heapq.heappop(heap)

heapq.heappop(list1)
print(list1)

>>>[3, 9, 8]

#heapq.heappushpop(heap, item)
#heapq.heapreplace(heap, item)
#heapq.merge(*iterables)
for x in heapq.merge([1,3,5],[7,9,10]):
    print(x, end=" ")
    
    >>> 1 3 5 7 9 10  

# 최대 힙 만들기
# 리스트 [3,2,5,1,7,8,2]
# 트리화 

# 왼쪽 자식의 인덱스 (i x 2) + 1,
# 오른쪽 자식의 인덱스 (i x 2) + 2

# 전체 길이를 반으로 나눕니다.
# 7 // 2 -> 3

# 인덱스가 3일때 자식이 없음 -> 넘긴다.
# 인덱스가 2일때 자식이 있고 5보다 큰 값이 8 있기때문에
# 인덱스 2와 6의 값을 교환해준다.

class Heapify(object):
    def __init__(self, data=None):
        self.data = data or []
        for i in range(len(data) // 2, -1, -1):
            self.__max_heapify__(i)
    def __repr__(self):
        return repr(self.data)
    def parent(self, i):
        if i & 1:
            return i >> 1
        
        else:
            return (i >> 1) -1
        
    def left_child(self, i):
        return (i << 1) + 1
    
    def right_child(self, i):
        return (i << 1) + 2
    
    def __max_heapify__(self, i):
        largest = i
        left = self.left_child(i)
        right = self.right_child(i)
        n = len(self.data)
        
        # 왼족 자식
        largest = (left < n and self.data[left] > self.data[i] and left or i)
        # 오른쪽 자식
        largest = (right < n and self.data[right] > self.data[largest] and right or largest)
        
        # 현재노드가 자식들보다 크다면 skip, 작다면 swap
        if i is not largest:
            self.data[i], self.data[largest] = self.data[largest], self.data[i]
            self.__max_heapify__(largest)
            
    def extract_max(self):
        n = len(self.data)
        max_element = self.data[0]
        self.data[0] = self.data[n - 1]
        self.data = self.data[:n - 1]
        self.__max_heapify__(0)
        return max_element
    
    def insert(self, item):
        i = len(self.data)
        self.data.append(item)
        while (i != 0) and item > self.data[self.parent(i)]:
            print(self.data)
            self.data[i] = self.data[self.parent(i)]
            i = self.parent(i)
        self.data[i] = item
def test_heapify():
    l1 = [3, 2, 5, 1, 7 , 8, 2]
    h = Heapify(l1)
    assert(h.extract_max() == 8) 
    print("테스트 통과")
    
if __name__ == "__main__":
    test_heapify()

# heapq 모듈을 사용해서 우선순위 큐 클래스를 구현을 해보겠습니다.

import heapq

class PriorityQueue(object):
    def __init__(self):
        # 큐를 담고 있을 리스트 변수
        self._queue = []
        # 큐의 요소를 개수를 가지고 있을 변수
        self._index = 0
        
    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1
    
    def pop(self):
        return heapq.heappop(self._queue)[-1]
    
class Item:
    def __init__(self, name):
        self.name = name
        
    def __repr__(self):
        return "Item{0!r}".format(self.name)
    
def test_priority_queue():
    q = PriorityQueue()
    q.push(Item('test1'), 1)
    q.push(Item('test3'), 4)
    q.push(Item('test7'), 3)
    
    assert(str(q.pop()) == "Item'test3'")
    print("테스트 통과")
    

if __name__ == "__main__":
    test_priority_queue()

# 연결 리스트
# 값과 다음 노드에 대한 포인터가 포함된 노드
# 비선형 리스트와, 선형 리스트
# 연결 리스트 -> 선형 리스트
# 마지막 노드는 항상 null 값-> 파이썬 None값
# 연결 리스트는 스택(새항목을 헤드에 추가),
# 큐(새 항목을 테일에 추가) 구현한다.
# 헤드 ? 테일?

class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer
        
    def getData(self):
        return self.value

    def getNext(self):
        return self.pointer
    
    def setData(self, newData):
        self.value = newData
        
    def setNext(self, newPointer):
        self.pointer = newPointer
        
if __name__ == "__main__":
    L = Node("A", Node("B", Node("C", Node("D"))))
    assert(L.pointer.pointer.value == 'C')
    
    print(L.getData())
    print(L.getNext().getData())
    print(L.setData('aa'))
    print(L.setNext(Node('E')))
    print(L.getData())
    print(L.getNext().getData())

>>>
A
B
None
None
aa
E

# 이 연결리스트로 이루어진 후입선출 연결리스트를 만들어봅시다.

# 결과값
# 연결 리스트 출력:
# 4 3 2 1
#$ 인덱스가 2인 노드를 삭제후 연결 리스트 출력 :
# 4 3 1
# 값이 3인 노드 삭제 후 연결 리스트 출력
# 4 1
#값이 15인 노드 추가 후 연결 리스트 출력
# 15 4 1
# 모든 노드 모두 삭제 후 연결 리스트 출력 :
#

class LinkedListLIFO(object):
    def __init__(self):
        self.head = None
        self.length = 0
        
    # 헤드에서 각 노드의 값을 출력하빈다.
    def _printList(self):
        node = self.head
        while node :
            print(node.value, end = " ")
            node = node.pointer 
        print()
        
    # 이전 노드를 기반으로 노드를 삭제
    def _delete(self, prev, node):
        self.length -= 1
        if not prev:
            self.head = node.pointer
        else:
            prev.pointer = node.pointer
            
    # 새 노드를 추가합니다. 다음 노드로 헤드를 가르키고
    # 헤드는 새 노드를 가르킵니다.
    def _add(self, value):
        self.length += 1
        self.head = Node(value, self.head)
        
    # 인덱스로 노드를 찾습니다.
    def _find(self, index):
        prev = None
        node = self.head
        i = 0
        while node and i < index:
            prev = node
            node = node.pointer
            i += 1
        return node, prev, i
    
    # 값으로 노드를 찾습니다.
    def _find_by_value(self, value):
        prev = None
        node = self.head
        found = False
        while node and not found:
            if node.value == value:
                found = True
            else:
                prev = node
                node = node.pointer
        return node, prev, found
    
    # 인덱스에 해당하는 노드를 찾아서 삭제
    def deleteNode(self, index):
        node, prev, i = self._find(index)
        if index == i:
            self._delete(prev, node)
        else:
            print(f"인덱스 {index}에 해당하는 노드가 없습니다.")
    # 값에 해당하는 노드를 찾아서 삭제
    def deleteNodeByValue(self, value):
        node, prev, found = self._find_by_value(value)
        if found:
            self._delete(prev, node)
        else:
            print(f"값 {value}에 해당하는 노드가 없습니다.")
            
if __name__ == "__main__":
    ll = LinkedListLIFO()
    for i in range(1, 5):
        ll._add(i)
    print("연결리스트 출력")
    ll._printList()
    print("인덱스 2인 노드 삭제후, 연결 리스트 출력")
    ll.deleteNode(2)
    ll._printList()
    print("값이 3인 노드 삭제 후, 연결 리스트 출력")
    ll.deleteNodeByValue(3)
    ll._printList()
    print("값이 15인 노드 추가 후, 연결리스트 출력")
    ll._add(15)
    ll._printList()
    print("모든 노드 삭제 후 연결리스트 출력")
    for i in range(ll.length-1, -1, -1):
        ll.deleteNode(i)
    ll._printList()
    
>>>연결리스트 출력
4 3 2 1 
인덱스 2인 노드 삭제후, 연결 리스트 출력
4 3 1 
값이 3인 노드 삭제 후, 연결 리스트 출력
4 1 
값이 15인 노드 추가 후, 연결리스트 출력
15 4 1 
모든 노드 삭제 후 연결리스트 출력

# 선입선출 연결 리스트
class LinkedListFIFO(object):
    def __init__(self):
        self.head = None
        self.length = 0
        self.tail = None
        
    #각 헤드로부터 노드의 값을 출력합니다.
    def _printList(self):
        node = self.head
        while node:
            print(node.value, end=' ')
            node = node.pointer
        print()
        
    # 첫번째 위치에 노드를 추가합니다.
    def _addFirst(self, value):
        self.length = 1
        node = Node(value)
        self.head = node
        self.tail = node
    # 첫번째 위치에 노드를 삭제합니다.
    def _deleteFirst(self):
        self.length = 0
        self.head = None
        self.tail = None
        print("연결 리스트가 비었습니다.")
        
    # 새 녿르르 추가합니다. 테일이 있다면 테일의 다음 노드는
    # 새 노드를 가르키고, 테일을 새 노드를 가르킵니다.
    def _add(self, value):
        self.length += 1
        node = Node(value)
        if self.tail:
            self.tail.pointer = node
        self.tail = node
        
    # 새 노드를 추가합니다.
    def addNode(self, value):
        if not self.head:
            self._addFirst(value)
        else:
            self._add(value)
    # 인덱스로 노드를 찾습니다.
    def _find(self, index):
        prev = None
        node = self.head
        i = 0
        while node and i < index:
            prev = node
            node = node.pointer
            i += 1
        return node, prev, i
    
    # 값으로 노드를 찾는다.
    def _find_by_value(self, value):
        prev = None
        node = self.head
        found = False
        while node and not found:
            if node.value== value:
                found = True
            else:
                prev = node
                node = node.pointer
            return node, prev, found
        
    # 인덱스에 해당하는 도르를 삭제합니다.
    def deleteNode(self, index):
        if not self.head or not self.head.pointer:
            self._deleteFirst()
        else:
            node, prev, i = self._find(index)
            if i == index and node:
                self.length -= 1
                if i == 0 or not prev:
                    self.head = node.pointer
                    self.tail = node.pointer
                else:
                    prev.pointer = node.pointer
            else:
                print("인덱스 {0}에 해당하는 노드가 없습니다.".format(index))
                
    # 값에 해당하는 녿를 삭제
    def deleteByValue(self, value):
        if not self.head or not self.head.pointer:
            self._deleteFirst()
        else:
            node, prev, i = self._find_by_value(value)
            if node and node.value == value:
                self.length -= 1
                if i == 0 or not prev:
                    self.head = node.pointer
                    self.tail = node.pointer
                else:
                    prev.pointer = node.pointer
            else:
                print("인덱스 {0}에 해당하는 노드가 없습니다.".format(value))
if __name__ == "__main__":
    ll = LinkedListFIFO()
    for i in range(1, 5):
        ll.addNode(i)
    print("연결리스트 출력:")
    ll._printList()
    print("인덱스가 2인 노드 삭제후 연결리스트 출력:")
    ll.deleteNode(2)
    ll._printList()
    print("값이 15인 노드 추가후 연결리스트 출력 :")
    ll.addNode(15)
    ll._printList()
    print("모든 노드 삭제후 연결리스트 출력 :")
    for i in range(ll.length-1, -1, -1):
        ll.deleteNode(i)
    ll._printList()

# 해시테이블 -> 수업진도가 그래프에 도달했을때 다시한번!!
# 키를 값에 연결해서 하나의 키가 0 또는 1개의 값과 연관되게 만듭니다.
# 각 키는 해시 함수를 계산할수 있어야 합니다.
# 해시테이블은 해시 버킷의 배열로 구성됩니다.
# 예)
# 해시값 : 42
# 5개의 버킷 -> 나머지 연산을 사용 버킷 2에 매핑
# 버킷 2(42 mod 5)

# 스택 문제 1)
# 문자열을 연숙으로 뒤집에서 출력해봅시다.
# 파이썬은 쉽고 재밌다.
# .다밌재 고쉽 은썬이파
def reversed_string(str1):
    s = Stack()
    revStr = ''
    
    for c in str1:
        s.push(c)
        
    while not s.isEmpty():
        revStr += s.pop()
        
    return revStr

if __name__ == "__main__":
    str1 = "파이썬은 쉽고 재밌습니다."
    print(str1)
    print(reversed_string(str1))
    
>>>파이썬은 쉽고 재밌습니다.
>>>.다니습밌재 고쉽 은썬이파

# 스택 문제 2)
# 괄호의 균형이 맞는지 확인하는 문제
# '((()))'
# '(()'
def balance(str1):
    s = Stack()
    balanced = True
    index = 0
    
    while index < len(str1) and balanced:
        symbol = str1[index]
        
        
        if symbol == '(':
            s.push(symbol)
            
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index += 1
        
    if balanced and s.isEmpty():
        return True
    
    else:
        return False
    
if __name__ == "__main__":
    print(balance('((()))'))
    print(balance('((())'))
    
 >>>True
 >>>False

# 10진수를 2진수로 바꾸기
# 스택을 이용해서

def dec2bin(decnum):
    s = Stack()
    str_aux = ""
    
    while decnum > 0:
        dig = decnum % 2
        decnum = decnum // 2
        s.push(dig)
        
    while not s.isEmpty():
        str_aux += str(s.pop())
        
    return str_aux

if __name__ == "__main__":
    decnum = 9
    print(dec2bin(decnum))
    
    >>>1001

def convert_from_decimal(number, base):
    multiplier, result = 1, 0
    while number > 0:
        result += number % base * multiplier
        multiplier *= 10
        number = number // base
    return result

def test_convert():
    number, base = 9, 2
    assert(convert_from_decimal(number, base) == 1001)
    print("테스트 통과!! 잘했습니다.")

if __name__ == "__main__":
    test_convert()
    
    
    >>>테스트 통과!! 잘했습니다.

# 문자열 뒤집기
def revert(str1):
    return str1[::-1]

revert("안녕하세요. 저는 파이썬이 너무 재밌습니다.")

>>>'.다니습밌재 무너 이썬이파 는저 .요세하녕안'

# 사용자가 문장을 매개변수에 적으면
# 그 매개변수를 뒤집에서 반환을 합니다.
# 파이썬 알고리즘은 너무 재밌습니다.
# 재밌습니다. 너무 알고리즘은 파이썬

def reversing_words(word):
    new_word = []
    words = word.split(" ")
    for word in words[::-1]:
        new_word.append(word)
    return " ".join(new_word)

if __name__ == "__main__":
    str1 = "파이썬 알고리즘은 너무 재밌습니다."
    str2 = reversing_words(str1)
    print(str2)
        
        >>>재밌습니다. 너무 알고리즘은 파이썬

# heapq 사용해서
# 정렬된 두 시퀸스를 적은 비용으로 병합해봅시다.

# heapq.merge(리스트1, 리스트 2)

import heapq

def merge(seq1, seq2):
    result = []
    for c in heapq.merge(seq1, seq2):
        result.append(c)
    return result

if __name__ == "__main__":
    seq1 = [1,2,3,8,9,10]
    seq2 = [2,3,4,5,6,7,9]
    seq3 = seq1 + seq2
    print(sorted(seq3))
    
    seq4 = merge(seq1, seq2)
    
    print(seq4)
    
    assert(merge(seq1, seq2) == (seq3))
    print("ㅌㅅㅌㅌㄱ")
    
   >>>[1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 9, 10]
	>>>[1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 9, 10] 

# 연결리스트
# 연결리스트 끝에서 k번째 항목을 찾아봅시다.
# 만약에 k = 3
# 연결리스트 : 1 2 3 4 5 6 7 8 9 10
# 연결 리스트 끝에서 3번째 항목은 8입니다.

class kFromLast(LinkedListFIFO):
    def find_k_to_last(self, k):
        p1, p2 = self.head, self.head
        i = 0
        while p1:
            if i > k - 1:
                try:
                    p2 = p2.pointer
                except AttributeError:
                    break
            p1 = p1.pointer
            i += 1
        return p2.value
    
if __name__ == "__main__":
    ll = kFromLast()
    for i in range(1, 11):
        ll.addNode(i)
    print("연결 리스트 :")
    ll._printList()
    k = 3
    k_from_Last = ll.find_k_to_last(k)
    print("연결 리스트 끝에서 {0}번째 항목은 {1}입니다.".format(k, k_from_Last))

>>>연결 리스트 :
1 2 3 4 5 6 7 8 9 10 
연결 리스트 끝에서 3번째 항목은 8입니다.

# 연결 리스트 분할하기
# 숫자가 담긴 연결 리스트에서 한 항목을 선택했을 때
# 그 항목의 값의 왼쪽에는 작은 숫자 항목만 나오고
# 오른쪽에는 큰 숫자 항목만 나오도록 연결 리스트를 분할해보자!
# 분할 전:
# 6 7 3 4 9 5 1 2 8
# 분할 후
# 3 4 5 1 2 6 7 9 8

def partList(ll, n):
    more = LinkedListFIFO()
    less = LinkedListFIFO()
    
    node = ll.head
    
    while node:
        item = node.value
        
        if item < n:
            less.addNode(item)
        elif item > n:
            more.addNode(item)
            
        node = node.pointer
        
    less.addNode(n)
    nodemore = more.head
    
    while nodemore:
        less.addNode(nodemore.value)
        nodemore = nodemore.pointer
    return less

if __name__ == "__main__":
    ll = LinkedListFIFO()
    l = [6,7,3,4,9,5,1,2,8]
    for i in l:
        ll.addNode(i)
        
    print("분할 전:")
    ll._printList()
    
    print("분할 후:")
    newll = partList(ll, 5)
    newll._printList()
    
>>>
분할 전:
6 7 3 4 9 5 1 2 8 
분할 후:
3 4 1 2 5 6 7 9 8