프로그래머스 강좌, 자료구조와 알고리즘 - 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 문안에서 할당하여 바로 비교하는 연산은 불가하다고 한다.  [참조](https://stackoverflow.com/questions/19767891/python-assign-value-to-variable-during-condition-in-while-loop/19767980)

## 13강. 후위 표기 수식 계산
### 실습
목표: 후위 표기법으로 전달받은 수식을 연산하여 반환
```python
# 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()

좋은 웹페이지 즐겨찾기