(알고리즘 문제) 동물 보호소
동물 보호소 코딩인터뷰 완전분석 - 게일 라크만 맥도웰
먼저 들어온 동물이 먼저 나가는 동물 보호소(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)