C++로 전화번호부 시스템 설계하기

이번 글에서는 다음과 같은 연산을 지원하는 전화번호부(Phone Directory)를 C++로 설계하는 방법을 알아보겠습니다.

get – 아직 아무에게도 할당되지 않은 번호를 하나 반환합니다.
check – 특정 번호가 현재 사용 가능한지 여부를 확인합니다.
release – 사용 중이던 번호를 회수하여 다시 사용할 수 있도록 반환합니다.

생성자(initializer)를 통해 처음에 총 n개의 번호를 초기화할 수 있습니다.

해결 접근 방법

이 문제는 집합(set)과 큐(queue) 두 가지 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.

사용 중인 번호를 관리할 집합 s를 정의합니다.
아직 배정 가능한 번호를 보관할 큐 available을 정의합니다.
생성자는 maxNumbers를 매개변수로 받습니다.
N := maxNumbers로 설정합니다.
i := 0부터 i < N까지 반복하면서 각 번호 i를 available 큐에 삽입합니다.

get() 함수

available의 크기가 0이면 -1을 반환합니다.
x := available의 첫 번째 원소를 가져옵니다.
x를 집합 s에 삽입합니다.
available에서 해당 원소를 제거합니다.
x를 반환합니다.

check() 함수

number가 N 이상이거나 0 미만이면 false를 반환합니다.
그렇지 않으면 number가 집합 s에 없는 경우 true를 반환합니다(사용 가능 상태).

release() 함수

check(number)가 true라면 이미 사용 가능한 번호이므로 그대로 종료합니다.
x := number로 설정합니다.
s에서 x를 삭제합니다.
x를 available 큐에 삽입하여 재사용 대기열에 넣습니다.

예제 코드

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class PhoneDirectory {
public:
    set<int> s;
    queue<int> available;
    int N;
    PhoneDirectory(int maxNumbers){
        N = maxNumbers;
        for (int i = 0; i < N; i++) {
            available.push(i);
        }
    }
    int get(){
        if (available.size() == 0)
            return -1;
        int x = available.front();
        s.insert(x);
        available.pop();
        return x;
    }
    bool check(int number){
        if (number >= N || number < 0)
            return false;
        return s.find(number) == s.end();
    }
    void release(int number){
        if (check(number))
            return;
        int x = number;
        s.erase(x);
        available.push(x);
    }
};
main(){
    PhoneDirectory ob(3);
    cout << (ob.get()) << endl;
    cout << (ob.get()) << endl;
    cout << (ob.check(2)) << endl;
    cout << (ob.get()) << endl;
    cout << (ob.check(2)) << endl;
    ob.release(2);
    cout << (ob.check(2)) << endl;
}

입력

ob.get();
ob.get();
ob.check(2);
ob.get();
ob.check(2);
ob.release(2);
ob.check(2);

출력

동작 과정 설명

최대 3개의 번호(0, 1, 2)로 초기화된 상황을 가정해 보겠습니다.

첫 번째 get() 호출 → 번호 0이 배정되고, 결과는 0입니다.
두 번째 get() 호출 → 번호 1이 배정되고, 결과는 1입니다.
check(2) 호출 → 번호 2는 아직 배정되지 않았으므로 true(1)입니다.
세 번째 get() 호출 → 번호 2가 배정되고, 결과는 2입니다.
check(2) 호출 → 번호 2는 이제 사용 중이므로 false(0)입니다.
release(2) 호출 후 check(2) 호출 → 번호 2가 회수되어 다시 사용 가능하므로 true(1)입니다.

이처럼 set과 queue를 조합하면 get, check, release 세 연산 모두 효율적으로 처리할 수 있는 전화번호부를 구현할 수 있습니다.