박종훈 알고리즘 블로그

(알고리즘 문제) 동물 보호소

동물 보호소 코딩인터뷰 완전분석 - 게일 라크만 맥도웰


먼저 들어온 동물이 먼저 나가는 동물 보호소(animal shelter)가 있다고 하자. 이 보호소는 개와 고양이만 수용한다. 사람들은 보호소에서 가장 오래된 동물부터 입양할 수 있는데, 개와 고양이 중 어떤 동물을 데려갈지 선택할 수 있다. 하지만 특정한 동물을 지정해 데려갈 수는 없다. 이 시스템을 자료구조로 구현하라. 이 자료구조는 enqueue, dequeueAny, dequeueDog, dequeueCat의 연산을 제공해야 한다. 기본적으로 탑재되어 있는 LinkedList 자료구조를 사용해도 좋다.

일단 기능 요구사항을 정리해보자.

  • enqueue : queue에 저장
  • dequeueAny : “먼저 들어온 동물이 먼저 나가는” 이라고 명시되어 있기 때문에, 개나 고양이 상관없이 오래된 동물을 dequeue.
  • dequeueDog : 개 queue 에서 dequeue
  • dequeueCat : 고양이 queue 에서 dequeue

순서를 고려해야 하기 때문에 각 동물에 순차적으로 id를 부여해 주었다.

class Animal:
    def __init__(self, id, name):
        self.id = id
        self.name = name

class AnimalShelter:
    def __init__(self):
        self.dogQueue = []
        self.catQueue = []
        self.animal_id = 0

    def enqueue(self, name, animal_type):
        self.animal_id += 1
        animal = Animal(self.animal_id, name)
        if animal_type == 'dog':
            self.dogQueue.append(animal)
        elif animal_type == 'cat':
            self.catQueue.append(animal)

    def dequeueAny(self):
        if not self.dogQueue:
            return self.dequeueCat()
        elif not self.catQueue:
            return self.dequeueDog()

        if self.dogQueue[0].id < self.catQueue[0].id:
            return self.dequeueDog()
        else:
            return self.dequeueCat()

    def dequeueDog(self):
        if self.dogQueue:
            return self.dogQueue.pop(0).name
        else:
            return None

    def dequeueCat(self):
        if self.catQueue:
            return self.catQueue.pop(0).name
        else:
            return None
shelter = AnimalShelter()
shelter.enqueue("멍멍이", "dog")
shelter.enqueue("야옹이", "cat")
shelter.enqueue("바둑이", "dog")
shelter.enqueue("흰둥이", "dog")
shelter.enqueue("개냥이", "cat")

# dog queue : 멍멍이(1) - 바둑이(3) - 흰둥이(4)
# cat queue : 야옹이(2) - 개냥이(5)

print(shelter.dequeueAny())

# dog queue : 바둑이(3) - 흰둥이(4)
# cat queue : 야옹이(2) - 개냥이(5)

print(shelter.dequeueDog())

# dog queue : 흰둥이(4)
# cat queue : 야옹이(2) - 개냥이(5)

print(shelter.dequeueCat())

# dog queue : 흰둥이(4)
# cat queue : 개냥이(5)

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , , Queue