[백준][C++] 5052. 전화번호 목록

string 형태의 전화번호 목록이 주어지면 해당 목록이 일관성 유무를 반환하는 문제이다.

여기서 일관성이 있다는 것은, 한 번호가 다른 번호의 접두어인 경우가 없다는 뜻이다.

 

이 문제를 선택한 이유는 트리 문제였기 때문이다.

그래서 웬만하면 트리로 풀고 싶었는데...

내 머리로는 이진트리밖에 생각이 나지 않아서 이걸로 어떻게 이 문제를 풀어야할지 감이 안잡혔다.

 

그래서 일단은 쉽게 정렬로 풀었다.

전화번호 목록을 오름차순으로 정렬한 다음, 앞에서부터 번호들을 비교해 이전 번호가 다음 번호의 접두어가 되는지 일일이 확인했다.

정렬만 하면 쉽게 해결됐던 문제...

 

[정렬로 해결한 코드]

// 5052_전화번호_목록
using namespace std;
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

int t; // test case
int n; // 전화번호 개수

bool consistency(vector<string> phone) {
	for (int i = 1; i < phone.size(); i++) {
		string cur = phone[i]; // 현재 번호
		string prev = phone[i - 1]; // 이전 번호 (비교대상)

		int cnt = 0; // 일치하는 숫자 개수
		for (int j = 0; j < prev.size(); j++) {
			if (cur[j] == prev[j]) cnt += 1;
			else continue;
		}

		if (cnt == prev.size()) return false;
	}

	return true;
}

int main() {
	scanf("%d", &t);

	for (int tc = 0; tc < t; tc++) {
		scanf("%d", &n);

		vector<string> phone;
		for (int i = 0; i < n; i++) {
			string num;
			cin >> num;
			phone.push_back(num);
		}

		sort(phone.begin(), phone.end()); // 오름차순 정렬
		bool answer = consistency(phone);

		if (answer == true) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

 

+++추가

 

찾아보니까 트리로 풀기 위해서는 트라이(TRIE)라는 알고리즘을 사용해야 한다고 한다.

트라이 알고리즘에 대한 정보는 아래 블로그를 참조했다.

twpower.github.io/187-trie-concept-and-basic-problem

[Algorithm] 트라이(Trie) 개념과 기본 문제

개념은 이해가는데... 솔직히 이런게 코테에서 나올까 싶긴 하다...

참고해서 코딩해보긴 했지만 시간 지나면 잊어버릴듯...ㅎ

 

[트라이(Trie) 알고리즘으로 해결한 코드]

// 5052_전화번호_목록
using namespace std;
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

int t; // test case
int n; // 전화번호 개수

struct Trie {
	bool is_eof; // 문자열의 끝이면 true
	Trie* child[10]; // 자식은 숫자 0 ~9 최대 10개

	Trie() : is_eof(false) { // child 생성
		memset(child, 0, sizeof(child));
	}
	~Trie() { // child 삭제
		for (int i = 0; i < 10; i++) {
			if (child[i]) delete child[i];
		}
	}

	/* 새로운 문자열 Trie에 추가 */
	void insert(const char* key) { 
		if (*key == '\0') { // 문자열 끝인 경우
			is_eof = true;
		}
		else {
			int idx = (int)(*key - '0');
			if (child[idx] == 0) child[idx] = new Trie();
			child[idx]->insert(key + 1);
		}
	}

	/* key에 해당하는 문자열을 접두어로 가지고 있는지 확인 */
	bool find(const char* key) { 
		if (*key == '\0') return true;
		if (is_eof) return false; // 문자열이 끝나기 전에 eof가 나오면 접두어가 있는 것

		int idx = (int)(*key - '0');
		return child[idx]->find(key + 1);
	}
};

int main() {
	scanf("%d", &t);

	for (int tc = 0; tc < t; tc++) {
		scanf("%d", &n);
		char phone[10001][11];

		Trie* root = new Trie();
		for (int i = 0; i < n; i++) {
			scanf("%s", &phone[i]);
			root->insert(phone[i]);
		}

		bool answer = true;
		for (int i = 0; i < n; i++) {
			if (root->find(phone[i]) == false) {
				answer = false;
				break;
			}
		}

		delete root;
		if (answer) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}