[코딩 인터뷰]자료구조 - 스택과 큐 문제(Python)

 

[ 한 개로 세 개 ]

 배열 한 개로 스택 세 개 구현

class threeInone:
    def __init__(self):
        self.items = []
        self.stackCnt = {1: 0, 2: 0, 3: 0}
        self.stackNumError = 'I have only 3 stacks'

    def pop(self, stackNum: int):
        idx = -1
        if stackNum not in self.stackCnt.keys():
            return self.stackNumError
        else:
            if self.stackCnt[stackNum] != 0:
                self.stackCnt[stackNum] -= 1
                for i in range(1, stackNum+1):
                    idx += self.stackCnt[i]
            else:
                return 'Error'
        return self.items.pop(idx)

    def push(self, stackNum: int, item):
        if stackNum not in self.stackCnt.keys():
            return self.stackNumError
        else:
            idx = 0
            for i in range(1, stackNum+1):
                idx += self.stackCnt[i]
            self.stackCnt[stackNum] += 1
        self.items.insert(idx, item)

    def peek(self, stackNum: int):
        if stackNum not in self.stackCnt.keys():
            return self.stackNumError
        else:
            idx = -1
            if self.stackCnt[stackNum] == 0:
                return 'Error'
            for i in range(1, stackNum+1):
                idx += self.stackCnt[i]
            return self.items[idx]

    def isEmpty(self, stackNum: int):
        if stackNum > 3:
            return self.stackNumError
        else:
            return self.stackCnt[stackNum] == 0

👀 stackCnt라는 dictionary를 만들어서 각 스택의 길이를 저장했습니다. 만약 dictionary를 사용하면 안 된다고 하면 각 스택의 길이를 저장할 수 있는 변수를 만들어서 사용하면 됩니다.

 

 

[ 스택 Min ]

 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min 함수 추가

class stackMin:
    def __init__(self):
        self.items = []
        self.minNum = float('inf')

    def pop(self):
        try:
            popValue = self.items.pop()
            if popValue == self.minNum:
                self.minNum = self.items.pop()
            return popValue
        except Exception as e:
            print(e)

    def push(self, item):
        if item <= self.minNum:
            self.items.append(self.minNum)
            self.minNum = item
        self.items.append(item)

    def min(self):
        return self.minNum if self.items else "Empty"

👀 최솟값을 저장할 수 있는 self.minNum라는 변수를 생성하고 push 할 때 push 한 값과 최솟값을 비교하여 최솟값을 minNum에 저장하고 원래 들고 있던 최솟값을 스택에 저장합니다. 그리고 pop 할 때 pop 한 값과 minNum이 같다면 minNum에 pop을 해줍니다.(즉, 스택의 마지막 값을 넣어주고 마지막 값을 삭제합니다.)

⭐ float('inf')는 양의 무한대를 의미합니다. 여기서는 minNum 시작 시 가장 큰 값을 주기 위하여 설정하였습니다.

 

 

[ 접시 무더기 ]

 여러 개의 스택으로 구성된 스택 모음을 만들고 내부에서 이전 스택이 지정된 용량을 초과하는 경우 새로운 스택을 자동으로 생성하는 SetOfStacks 구현

class SetOfStacks:
    def __init__(self):
        self.stacks = [[]]
        self.maxLength = 10

    def push(self, item):
        if len(self.stacks[-1]) == self.maxLength:
            self.stacks.append([])
        self.stacks[-1].append(item)

    def pop(self):
        try:
            popValue = self.stacks[-1].pop()
            if self.stacks[-1] == []:
                self.stacks.pop()
            return popValue
        except Exception as e:
            print(e)

    def popAt(self, index: int):
        if index > len(self.stacks) or self.stacks == [[]]:
            return 'Error'
        popValue = self.stacks[index].pop()
        for i in range(index, len(self.stacks)-1):
            self.stacks[i].append(self.stacks[i+1].pop(0))
        if self.stacks[-1] == [] and self.stacks != [[]]:
            self.stacks.pop()
        return popValue

👀 maxLength 변수로 용량을 지정하고 push/pop에 따라서 스택을 추가 및 삭제하도록 구현했습니다. popAt의 경우 원하는 특정 index를 넣을 경우 그 index의 스택에 pop 하고 한 칸씩 자리 이동하도록 구현했습니다.

 

 

[ 스택으로 큐 ]

 스택 2개로 큐 하나 구현

class twoStacksOneQueue:
    def __init__(self):
        self.newStack = []
        self.oldStack = []
        self.size = len(self.newStack) + len(self.oldStack)

    def add(self, item):
        self.newStack.append(item)

    def shiftStacks(self):
        if self.oldStack == []:
            while self.newStack != []:
                self.oldStack.append(self.newStack.pop())

    def remove(self):
        try:
            self.shiftStacks()
            self.oldStack.pop()
        except Exception as e:
            return e

    def peek(self):
        try:
            self.shiftStacks()
            return self.oldStack[-1]
        except Exception as e:
            return e

👀 굳이 구현하자면 스택 2개(Old: 추가되기 이전에 값들을 저장, New: 새롭게 추가되는 값을 저장)를 remove나 peek 때 New 값들을 전부 Old로 pop/push 하면 됩니다.

 

 

[ 스택 정렬 ]

 가장 작은 값이 위로 오도록 스택을 정렬하는 알고리즘

⭐ 스택은 push, pop, peek, isEmpty의 4가지 연산을 제공해야 합니다.

⭐ 스택▼

class Stack:
    def __init__(self):
        self.stack = []

    def pop(self):
        try:
            return self.stack.pop()
        except Exception as e:
            print(e)

    def push(self, item):
        self.stack.append(item)

    def peek(self):
        try:
            return self.stack[-1]
        except Exception as e:
            print(e)

    def isEmpty(self):
        return not self.stack

def sortStack(s: Stack):
    r = Stack()
    while not s.isEmpty():
        tmp = s.pop()
        while not r.isEmpty() and r.peek() > tmp:
            s.push(r.pop())
        r.push(tmp)
    while not r.isEmpty():
        s.push(r.pop())

👀 사실 python에서 Stack을 list로 만들면 stack.sort(reverse=True)를 사용하면 쉽게 정렬됩니다. 위의 코드는 O(N^2)의 시간 복잡도를 가지지만 sort를 사용하면 시간 복잡도는 O(NlogN)입니다.

 

 

[ 동물 보호소 ]

 먼저 들어온 동물이 먼저 나가는 동물 보호소에서 동물의 종류만 선택하여 데려가는 알고리즘 (동물의 종류는 개와 고양이로 한정)

⭐ 큐▼

class Queue:
    def __init__(self):
        self.queue = []

    def add(self, item):
        self.queue.append(item)

    def remove(self):
        try:
            self.queue.pop(0)
        except Exception as e:
            return e

    def peek(self):
        try:
            return self.queue[0]
        except Exception as e:
            return e

    def isEmpty(self):
        return not self.queue

import datetime
class Animal:
    def __init__(self, n: str = "NO NAME", s: str = "NO SPECIES"):
        self.name = n
        self.species = s
        self.rescueDate = datetime.datetime.now()

class animalShelter:
    def __init__(self):
        self.animal = {"dog": Queue(), "cat": Queue()}

    def rescue(self, animal: str, name: str):
        tmp = Animal(name, animal)
        self.animal[animal].add(tmp)

    def adoption(self, animal: str = ""):
        if len(animal) > 0 and animal not in self.animal.keys():
            return f'No {animal}'
        if animal == "":
            if self.animal["dog"].isEmpty() and self.animal["cat"].isEmpty():
                return 'No animals'
            dog = self.animal["dog"].peek() if not self.animal["dog"].isEmpty() else Animal()
            cat = self.animal["cat"].peek() if not self.animal["cat"].isEmpty() else Animal()
            animal = dog.species if dog.rescueDate < cat.rescueDate else cat.species

        if self.animal[animal].isEmpty():
            return 'No animals'
        else:
            newFamily = self.animal[animal].peek()
            self.animal[animal].remove()
            return f"Hello, This is {newFamily.name}."

👀 동물 구조 시 동시에 들어가는 시간은 없다고 가정한 뒤 코드를 작성하였습니다. animal이라는 class를 만든 뒤 add 할 때의 시간을 같이 기록하였습니다. 동물을 입양할 때 어떤 동물이든지 상관없을 때에는 시간을 비교한 뒤 가장 오래 있던 동물이 입양되도록 설정하였습니다.