프로그래머스 강좌, 자료구조와 알고리즘 - 2

자료구조와 알고리즘 - 2 link

10강. 양뱡향 연결 리스트(Doubly Linked Lists)

노드간 참조공간을 뒤따라 오는 개체 참조 외에도 앞서오는 개체 참조공간도 생성하여
앞에서 뒤로, 뒤에서 앞으로 링크가 되어있는 형태

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None
        
class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'
        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
        return curr

    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

실습1

목표: 리스트를 역순으로 출력하는 함수 구성

 def reverse(self):
     target = self.tail
     returnList = []

     while target.prev is not self.head:
         returnList.append(target.prev.data)
         target = target.prev
     
      return returnList

실습2

목표: 선택된 next 앞에 newNode 삽입

    def insertBefore(self, next, newNode):
        if next is self.head:
            return False
            
        next.prev.next = newNode
        newNode.prev = next.prev
        newNode.next = next
        next.prev = newNode

        self.nodeCount += 1
        return True

실습3

목표: 값을 뽑아내는 popAfter(), popBefore(), popAt() 구현 / popAt()은 popAfter()나 popBefore()를 사용해 구현

    def popAfter(self, prev):
        if prev is self.tail:
            return None
        targetNode = prev.next

        prev.next = targetNode.next
        targetNode.next.prev = prev
        self.nodeCount -= 1
        return targetNode.data

    def popBefore(self, next):
        if next is self.head:
            return None
        targetNode = next.prev

        next.prev = targetNode.prev
        targetNode.prev.next = next
        self.nodeCount -= 1
        return targetNode.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        if self.nodeCount is 1 or pos is 1:
            return self.popAfter(self.head)
        else:
            prevNode = self.getAt(pos-1)
            return self.popAfter(prevNode)

실습4

목표: 전달받은 리스트를 뒤에 병합하는 기능 구현

    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        
        self.nodeCount += L.nodeCount

다른사람의 풀이를 통해 python은 , 를 통해 한번에 여러 대입이 가능함을 알았다. 상당히 직관적인 프로그래밍이 가능한 것 같다. 하지만 가독성으로는 기존 방식이 더 유리한듯 하다.

11강. 스택(Stacks)

후입선출(LIFO; Last In - First Out)로써 데이터의 입출이 동작하는 형태의 자료구조

• size(): 현재 스택에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 스택이 비어 있는지를 판단 (size() == 0?)
• push(x): 데이터 원소 x 를 스택에 추가
• pop(): 스택에 가장 나중에 저장된 데이터 원소를 제거 (또한, 반환)
• peek(): 스택에 가장 나중에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class ArrayStack:
 def __init__(self):
  self.data = []
 def size(self):
  return len(self.data)
 def isEmpty(self):
  return self.size() == 0
 def push(self, item):
  self.data.append(item)
 def pop(self):
  return self.data.pop()
 def peek(self):
  return self.data[-1]

class LinkedListStack:
 def __init__(self):
  self.data = DoublyLinkedList()
 def size(self):
  return self.data.getLength()
 def isEmpty(self):
  return self.size() == 0
 def push(self, item):
  node = Node(item)
  self.data.insertAt(self.size() + 1, node)
 def pop(self):
  return self.data.popAt(self.size())
 def peek(self):
  return self.data.getAt(self.size()).data

실습

목표: stack 을 이용한 완성된 괄호( ) 와 같은 형태가 존재 여부를 확인하는 기능

class ArrayStack:
    def __init__(self):
        self.data = []
    def size(self):
        return len(self.data)
    def isEmpty(self):
        return self.size() == 0
    def push(self, item):
        self.data.append(item)
    def pop(self):
        return self.data.pop()
    def peek(self):
        return self.data[-1]

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':
         S.push(c)
        elif c in match:
            if S.isEmpty():
                return False
            else:
             t = match[c]
                if t != S.pop():
                    return False
    return S.isEmpty()

12강. 스택의 응용 - 수식의 후위 표기법 (Postfix Notation)

중위표기법 (A+(B*C))-(D/E) - 연산자를 피연산자 사이에 표시, 일반적인 표기법
전위표기법 -+A*BC/DE - 연산자를 먼저, 피연산자를 나중에 표시
후위표기법 ABC*+DE/- - 피연산자를 먼저, 연산자를 나중에 표시

실습

목표: 괄호 유무에 상관없이 중위 표기를 후위 표기로 변경하는 기능 구현

에러 수정필요

def solution(S):
    opStack = ArrayStack()
    answer = ''
    
    for c in S:
        if c in prec:
            if c is not '(' and not opStack.isEmpty() and prec[opStack.peek()] >= prec[c]:
                answer += opStack.pop()
            opStack.push(c)
        elif c is ')':
            while True:
                op = opStack.pop()
                if op is not '(':
                 break
                answer += op
        else:
            answer += c
            
    while not opStack.isEmpty():
        op = opStack.pop()
        if op is not '(':
            answer += op
        
    return answer

A-(B-C)-D*(E/F)+G 처리 요청시, ABC--DEF/*-G+ 가 아닌 ABC--DEF/*G+-로 처리된다. 이유는?

python에선 값을 while 문안에서 할당하여 바로 비교하는 연산은 불가하다고 한다. 참조

13강. 후위 표기 수식 계산

실습

목표: 후위 표기법으로 전달받은 수식을 연산하여 반환

# infixToPostfix 메소드는 12강의 solution 사용

def postfixEval(tokenList):
    evalStack = ArrayStack()
    
    for t in tokenList:
        if isinstance(t,int):
            evalStack.push(t)
        else: #isOperator
            y = evalStack.pop()
            x = evalStack.pop()
            if t is '+':
                evalStack.push(x + y)
            elif t is '-':
                evalStack.push(x - y)
            elif t is '*':
                evalStack.push(x * y)
            else:
                evalStack.push(x / y)
    
    return evalStack.peek()