[코딩인터뷰 완전정복] 3.6 동물 보호소

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

 

#include <iostream>

#include <queue>

class Animal {

public:

    int num;

    Animal(int n) { num = n; }

};

class Dog : public Animal { 

public : 

    Dog(int n) : Animal(n) {}

};

class Cat : public Animal {

public:

    Cat(int n) : Animal(n) {}

};

class DogCatQueue{

private:

    std::queue<Dog> dogQueue;

    std::queue<Cat> catQueue;

    std::queue<bool> indexQueue;

    int catCnt;

    int dogCnt;

public:

    DogCatQueue() {

        catCnt = 0;

        dogCnt = 0;

    }

    void enqueue(Cat type) {

        catQueue.push(type);

        indexQueue.push(false);

    }

    void enqueue(Dog type) {

        dogQueue.push(type);

        indexQueue.push(true);

    }

    Animal dequeueAny() {

        bool out = indexQueue.front();

        if (out) {

            return dequeueDog();

        } else {

            return dequeueCat();

        }

        return out;

    }

    Cat dequeueCat() {

        Cat out = catQueue.front();

        catQueue.pop();

        if (!indexQueue.front())

            indexQueue.pop();

        else

            catCnt++;

        while (dogCnt != 0 && indexQueue.front()) {

            indexQueue.pop();

            dogCnt--;

        }

        return out;

    }

    Dog dequeueDog() {

        Dog out = dogQueue.front();

        dogQueue.pop();

        if (indexQueue.front())

            indexQueue.pop();

        else

            dogCnt++;

        while (catCnt != 0 && !indexQueue.front()) {

            indexQueue.pop();

            catCnt--;

        }

        return out;

    }

};

 

개와 고양이, 들어올 순서를 저장하는 queue 3개를 만든다.

enqueue - 개가 들어올 경우 개를 저장하는 큐에, 고양이가 들어올 경우 고양이를 저장하는 큐에 각각 저장한 후 index큐를 갱신 해준다.

dequeueDog, dequeueCat - 해당 큐에서 하나를 꺼내서 반환한다. index큐의 앞에 있는 원소를 확인한 후 꺼낸 동물과 일치하면 pop한다. 꺼낸 동물과 다르다면 count를 1올려준다. index큐를 pop한 뒤에 count를 확인해 1이상이고 front와 일치하면 count가 0이 되거나 일치하지 않을 때 까지 pop한다.

dequeueAny - index큐을 확인해 dequeueDog또는 dequeueCat을 반환한다.