[알고리즘문제] 전화 수신 전환 문제

재미있는(지는 모르겠지만. ㅎㅎㅎ) 알고리즘 문제입니다.

한번 다같이 풀어보아요~

 

[문제]

 우리 컴퓨터 회사는 직원이 출장이나 휴가 등으로 출근하지 않을 때 전화가 걸려오면, 다른 직원의 전화기에 벨이 울려서 전화를 받을 수 있도록 하는 수신 전환 기능을 이용하고 있다. 직원은 출근하지 않을 때는 걸려온 전화가 자동 수신 전환이 되도록 수신 전환하려는 전화번호를 입력한다. 다음에 출근하면 자신의 전화에 설정된 수신 전환을 해제한다.

 

 회사 내에 있는 전화 교환기는 어떤 전화번호가 다른 번호로 수신전환 되어있는지 리스트를 보관하고 있다. 문제는 어떤 번호로 전화가 걸려왔을 때, 어느 전화기 벨을 울려야하는지를 결정하는 프로그램을 작성하는 것이다. 회사 내에서는 사용하는 전화번호는 모두 4자리이고, 전화 번호 0000은 특별한 목적으로 사용하기 위해서 남겨두기로 한다.
 

 예를 들어서 3366번으로 걸려온 전화는 3366번 전화가 수신 전환되어 있지 않다면, 당연히 3366번 전화기 벨이 울려야 한다. 그러나 3366번이 3356번으로, 그리고 3356은 0154로 수신 전환되어 있다면, 3366으로 걸려온 전화는 수신 전환되어서 결국 0154번 전화기 벨이 울려야 할 것이다.

 

 3366번은 3356으로, 3356은 0154로, 그리고 0154가 다시 3366으로 수신 전환되어 있다면 이들 번호로 걸려온 전화는 영원히 수신 전환되어 버리는 문제가 발생한다. 이런 경우는 0000번 전화기 벨이 울려서 전화를 받을 수 있도록 한다. 0000번 전화는 다른 전화를 수신 전환할 수 없다.

 

 

[답안]

아래는 C언어로 링크드 리스트(Linked List)를 활용하여 문제를 해결한 답안입니다.

오래 전에 작성한 답변이라 소스 코드가 조금 세련되지 못했을 수도 있습니다.^^

 

제가 작성한 답안은 해결 법중의 하나로 다른 여러 해결법이 있을 수 있으며, 소스에는 가능한 자세한 주석을 달아놓았습니다.

 

[입력 형식]

   입력 파일의 이름은 INPUT.TXT이다. 첫줄에는 걸려온 전화번호가 입력된다. 전화번호는 십진수로 4자리가 주어진다. 둘째 줄부터 마지막 줄까지는 한 줄에 전화번호의 쌍이 하나씩 주어진다. 전화번호의 쌍 xxxx, yyyy가 의미하는 것은 xxxx번 전화가 yyyy로 수신전환 되어 있다는 것을 말한다. xxxx번 전화가 yyyy와 zzzz로 동시에 수신 전환될 수는 없음에 주의한다. 입력 파일에는 콤마가 없고, 두 전화번호 사이에 빈칸이 하나 있다. 전화번호의 쌍은 1,000개를 넘지 않는다.
 
[출력 형식]
  출력 파일의 이름은 OUTPUT.TXT이다. 첫 줄에 벨이 울려야할 전화기의 전화번호를 출력한다. 

 

#include <stdio.h> // printf()
#include <conio.h> // getch()
#include <string.h> // strcpy()
#include <malloc.h> // malloc()
#include <stdlib.h> // atoi()

 

int count = 0, sCount = 0; // count : 총 등록된 전화번호 수, sCound : 이미 한번 검사된 전화번호의 수 (무한 루프를 도는지 체크하기 위해서)
int searchPhone = 0; // 사용자가 전화한 번호. Input.txt 에서 가장 처음에 입력된 전화번호
int store[1000] = {0, }; // 무한 루프를 체크하기 위하여 이미 한번 검사된 전화번호를 임시로 저장할 배열

 

typedef struct TelData // 전화번호 정보 구조체
{

int phone; // 첫번째 전화번호
int link; // 연결을 위해 돌려놓은 전화번호 (두번째 전화번호)
struct TelData *next; // 다음 구조체를 가리키기 위한 포인터 변수

} telephone;

 

telephone *head, *tail; // 머리 노드, 꼬리 노드

 

void InitialWork(); // 링크드 리스트 초기화
void LoadFileData(); // Input.txt 파일로부터 데이터 읽어들이기

int  Search(); // 결과물(연결될 최종 전화번호 찾기) 찾기
void OutputResult(int result); // Output.txt 파일에 결과 쓰기, result : 최종 전화번호
void InsertPhone(int phone, int link); // Input.txt 파일로부터 전화번호를 읽어들여 링크드 리스트에 연결하기

 

void main()
{

InitialWork(); // 링크드 리스트 초기화
LoadFileData(); // 파일로부터 전화번호 읽어들여 링크드 리스트로 저장하기
OutputResult(Search()); // 최종 전화번호를 찾아 결과를 출력하기

getch();

}

 

int Search() // 최종 전화번호 찾기
{

telephone *cur = head->next;
int compare = searchPhone, i;
bool flag = false;

 

while(cur != tail) // 링크드 리스트가 끝날 때까지
{

if(cur->phone == compare) // 걸려온 전화번호가 수신 전환된 전화번호 라면
{

for(i = 0; i < sCount; i++) // 전화번호가 무한 루프인지 체크
{

if(store[i] == compare) // 무한 루프를 돌고 있다면
{

compare = 0; // 0값을 준다.
flag = true; 
break;

}

}

 

if(flag == true) // 무한 루프였다면 while문을 종료한다. 무한 루프라면 결과는 0000 이다.

break;

 

store[sCount++] = compare; // 방금 비교한 전화번호를 따로 저장한다. (무한 루프를 체크하기 위해)

compare = cur->link; // 새로 수신 전환된 전화번호가 존재하는지 체크하기 위한 작업
cur = head->next; // 다시 처음으로
continue;

}

cur = cur->next; // 걸려온 전화번호를 찾지 못했으면 다음 줄의 전화번호와 비교하기 위해 다음 노드로 이동

}

 

return compare; // 최종 전화번호를 return한다.

}

 

void InitialWork()
{

head = (telephone *)malloc(sizeof(telephone)); // 머리 노드에 메모리 할당
tail = (telephone *)malloc(sizeof(telephone)); // 꼬리 노드에 메모리 할당
head->next = tail; // 머리노드는 꼬리 노드를 가리킨다.
tail->next = tail; // 꼬리노드는 자기자신을 가리킨다.

}

 

void LoadFileData()
{

FILE *fp; // 파일 포인터 개체
char c; // 파일로부터 읽어들일 바이트 임시 저장 변수
char tempTel[5] = "", tempLink[5] = "", tempSearch[5] = ""; // 전화번호들을 임시로 저장하기 위한 변수, tempSearch에는 가장 처음에 입력된 전화번호가 기록된다.
int length = 0; // 각 전화번호들의 길이를 체크 (4자리)
bool flag = false; // 원래의 전화번호와 수신 전환된 전화번호를 나누어 저장하기 위해서 체크하는 변수

 

fp = fopen("Input.txt", "r"); // 파일 열기

 

for(int x = 0; x<5; x++) // 걸려온 전화번호를 얻는다. (파일의 맨 첫줄)

tempSearch[x] = getc(fp);

 

searchPhone = atoi(tempSearch); // 번호를 Int형으로 변환

 

while((c = getc(fp)) != EOF) // 파일의 끝까지 데이터를 차례차례 읽는다.
{

if(c == ' ') // 공란이라면 (원래의 전화번호와 수신 전환된 전화번호가 나누어진 부분)
{

flag = true; // 이제 부터는 수신 전환된 전화번호를 기록한다.
length = 0; // 전화 번호 배열 길이 변수 초기화
continue; // 루프 구문의 맨 위로 가서 새로 데이터를 읽는다.

}

 

if ((c >= '0' && c <= '9')) // 숫자라면
{

if(flag != true) // 원래의 전화번호 기록

tempTel[length++] = c;

else // 수신 전환된 전화번호 기록

tempLink[length++] = c;

}

 

if(c == '\n') // 한줄의 입력이 끝났다면
{

InsertPhone(atoi(tempTel), atoi(tempLink)); // 전화번호 구조체를 만들어 링크드 리스트에 저장

memcpy(tempTel, "", 5); // 임시 전화 번호 변수 초기화
memcpy(tempLink, "", 5);
length = 0; // 임시 전화 번호 길이 변수 초기화
flag = false; // 이제 부터는 원래의 전화번호를 기록한다.
count++; // 구조체 데이터 개수 하나 증가

}

}

 

InsertPhone(atoi(tempTel), atoi(tempLink)); // 마지막에 기록에서 빠진 데이터를 링크드 리스트에 추가

fclose(fp); // 파일 닫기

}

 

void InsertPhone(int phone, int link)
{

telephone *n, *headnext; // w : 새로운 전화번호를 저장할 포인터 변수, head의 다음 데이터(즉 첫번째 데이터)를 가지고 있을 포인터 변수
int c = 0; // 카운터를 세기 위한 변수

n = (telephone *)malloc(sizeof(telephone)); // 메모리 할당
 
n->phone = phone; // 새로 할당된 변수에 데이터 저장
n->link = link;

 

headnext = head->next; // headnext변수는 head 의 다음 노드 정보를 갖는다.
head->next = n; // head의 다음 노드는 새로운 데이터를 가리킨다.
n->next = headnext; // 새로운 데이터는 head의 다음 노드 정보를 가리킨다.

}

 

void OutputResult(int result)
{

FILE *fp; // 파일 포인터 개체
fp = fopen("Output.txt", "w"); // Output.txt 파일을 쓰기 형식으로 열기

 

if(sCount == 0) // 걸려온 전화가 결번이라면

fprintf(fp, "존재하지 않는 번호 입니다.");

else // 최종 전화번호를 적어준다.

fprintf(fp, "%04d", result); // int형으로 작업하였으므로 1000이하의 숫자(예 12)라도 4자리로 출력(예 0012)로 해준다.

 

printf("작업이 완료되었습니다. 결과는 Output.txt 에...^^");

fclose(fp); // 파일 개체 닫기

} 

 

 

소스코드, 샘플파일, 실행파일 받기

phone_algorithm.zip