[Programmers] 전화번호 목록(C++)

I 문제 소개

---

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 - 구조대 : 119
 - 박준영 : 97 674 223
 - 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

 - phone_book의 길이는 1 이상 1,000,000 이하입니다.
 - 각 전화번호의 길이는 1 이상 20 이하입니다.

---

II 문제 풀이

---

문제를 해석하자면 어떤 단어가 어떤 단어를 포함하고 있는지를 확인하면 되는데, 더군다나 그게 앞에서만 겹치는지 확인하면 된다는 점을 알 수 있다.

그래서 C++ string 클래스에 들어있는 str.compare을 이용해 판단하는 함수를 짜보았다.

왜냐하면 str.compare(0, str.size(), str2, 0, str.size())라고 인자를 입력할 경우 str과 str2를 각각 0에서부터 str.size()만큼의 문자열이 같은지 비교해 같으면 0을 반환해주기 때문이다.

그런데 이렇게 하면 시간 복잡도가 O(n^2)이 나오는데, 이 문제는 이전에 프로그래머스에서 풀었던 "완주하지 못한 선수" 문제처럼 효율성 테스트가 존재해 이중 루프의 형식으로 탐색해서 코드를 짜면 풀 수 없었다.

 

이 문제는 Trie라는 자료구조를 사용하는 문제다.

=> 이것이 문제의 핵심이다. Trie 자료구조는 문자열 여러개를 하나의 트리의 형태로 저장하는데, 겹치는 부분이 있는지 탐색하는 것에 최적화된 자료구조이다.

 

0. 초기 환경 설정(Trie 구현)

#include <string>
#include <cstring>
#include <vector>

using namespace std;

struct Trie {
	bool finish;
	Trie *next[10];

	Trie() :finish(false) {
		for (int i = 0;i < 10;i++)
			next[i] = 0;
	}
	~Trie() {
		for (int i = 0;i < 10;i++)
			if (next[i]) delete next[i];
	}

	void insert(char *key) {
		if (*key == '\0') finish = true;
		else {
			int cur = *key - '0';
			if (next[cur] == NULL) {
				next[cur] = new Trie();
			}
			next[cur]->insert(key + 1);
		}
	}

	bool find(char *key) {
		if (*key == '\0') return false;
		if (finish) return true;
		int cur = *key - '0';
		return next[cur]->find(key + 1);
	}
};

bool solution(vector<string> phone_book)
{
	bool answer = true;
	Trie *root = new Trie();
	int i;
	return answer;
}

Trie 자료구조는 이 문제를 풀면서 처음 접한 자료구조이기 때문에 구현은 구글링을 많이 참고했다.

만약 문자열이 숫자로 이루어진게 아니라 알파벳으로 이루어졌다면 10개가 아닌 26개로 선언해주어야 하고, 중간에 *key - '0'도 *key - ' A'의 형식으로 바꿔줘야 한다.

옛날에 C언어를 공부했을 때에는 Stack, Queue, Deque 정도의 자료구조를 직접 구현했었지만 C++에서는 그런 기본적인 자료구조는 라이브러리에서 다 지원해줘서 구조체와 포인터로 직접 구현해서 쓰는 자료구조는 정말 오랜만에 본다.

 

함수는 insert와 find가 있어 insert로 트리에 문자열을 저장하고, find로 겹치는 게 있는지 검사한다.

 

1. Trie에 문자열 입력(insert)

---

for (i = 0;i < phone_book.size();i++)
{
	char ch[20];
	strcpy(ch, phone_book[i].c_str());
	root->insert(ch);
}

구현한 Trie에 있는 함수들은 char 포인터를 매개변수로 받는데 phone_book 벡터의 원소는 string이기 때문에 한번에 insert로 넣을 수 없었다.

따라서 string을 char로 바꿔야했고, 이를 char 배열을 만든 후 c_str()를 이용해 strcpy로 복사하는 식으로 했다.

그 후 char 배열을 insert에 집어넣어주면 Trie에 phone_book 벡터 안에 있는 문자열을 모두 저장하는 것은 끝난다.

다만 C++에서 strcpy를 사용하기 위해서는 <cstring> 라이브러리를 사용해야하니 주의하자.

 

간혹 Visual Studio를 사용하면 컴파일할 때 strcpy 대신 strcpy_s를 쓰라고 오류가 뜨는데 용법상 차이가 없으니 그냥 바꿔주면 된다. 그런데 프로그래머스에 옮길때는 _s를 떼줘야한다. 불편하게시리 ㅡㅡ

 

2. 문자열 탐색(find)

---

for (i = 0;i < phone_book.size();i++)
{
	char ch[20];
	strcpy(ch, phone_book[i].c_str());
	if (root->find(ch))
	{
		answer = false;
		break;
	}
}

find도 매개변수가 char 포인터형식이기 때문에 임시 char 배열을 만들고 strcpy로 옮겨서 사용해야했다.

그리고 탐색시간을 조금이라도 단축시키기 위해 한번이라도 발견되면 반복문에서 탈출하게 했다.

해당사항이 한번도 없을 경우 겹치는 게 없다는 뜻이므로 answer는 처음에 값을 부여했던 그대로 true를 가질 것이고, 한번이라도 있을 경우 if문을 거쳐 false를 갖고 탈출할 것이다.

 

3. 최종

---

#include <string>
#include <cstring>
#include <vector>

using namespace std;

struct Trie {
	bool finish;
	Trie *next[10];

	Trie() :finish(false) {
		for (int i = 0;i < 10;i++)
			next[i] = 0;
	}
	~Trie() {
		for (int i = 0;i < 10;i++)
			if (next[i]) delete next[i];
	}

	void insert(char *key) {
		if (*key == '\0') finish = true;
		else {
			int cur = *key - '0';
			if (next[cur] == NULL) {
				next[cur] = new Trie();
			}
			next[cur]->insert(key + 1);
		}
	}

	bool find(char *key) {
		if (*key == '\0') return false;
		if (finish) return true;
		int cur = *key - '0';
		return next[cur]->find(key + 1);
	}
};

bool solution(vector<string> phone_book)
{
	bool answer = true;
	Trie *root = new Trie();
	int i;

	for (i = 0;i < phone_book.size();i++)
	{
		char ch[20];
		strcpy(ch, phone_book[i].c_str());
		root->insert(ch);
	}

	for (i = 0;i < phone_book.size();i++)
	{
		char ch[20];
		strcpy(ch, phone_book[i].c_str());
		if (root->find(ch))
		{
			answer = false;
			break;
		}
	}

	return answer;
}

이것이 최종적인 코드다. 합쳐놓고 보니 Trie 자료구조가 solution 함수보다 길다.

별거 아닌 문제였는데 Trie 자료구조를 알고 있는지가 관건이었던 것 같다.

 

III 느낀점

---

Trie 자료구조는 이 문제에서 처음 접했다.

처음에 이중루프로 풀었다가 시간초과의 벽에 막혔을 때, 문자열을 한번에 겹쳐서 저장할 수 없나라는 생각을 하다가 운좋게 Trie라는 자료구조를 찾아서 풀게 되었다.

 

왜 이 친구는 다른 자료구조들처럼 라이브러리로 지원을 안해줄까 아쉬움도 있었지만 시간복잡도를 O(n^2)에서 한번에 O(n)으로 줄여주는 게 매우 획기적이었다.

그래서 문자열을 다루는 데에 Trie 자료구조가 가장 이상적인 최강의 자료구조인가!?하면 공간복잡도의 측면까지 생각했을 때 아니라고 한다. 왜냐하면 문자 하나하나를 노드로 표현하는데, 각 노드마다 숫자라면 0~9 10개의 포인터 배열이, 알파벳이라면 A~Z 26개의 포인터 배열이 각각 있어야하기 때문이다.

 

그렇지만 이러한 형태의 문제를 풀 때 열쇠가 될 수 있음은 분명하다. 앞으로 Trie 자료구조와 관련된 문제를 풀면서 공부해볼 생각이다!

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Programmers 전화번호 목록 C++

프로그래머스 전화번호 목록 C++