[G4] 백준 5052번 전화번호 목록 C++ 트라이, 문자열

리뷰

 

접두사가 동일한 전화번호가 있는지 찾고, 있으면 YES를 없으면 NO를 출력하는 문제

https://www.acmicpc.net/problem/5052

 

전역 변수

• tc, n : 테스트케이스의 개수 tc, 각 테케마다 입력되는 전화번호의 개수 n
• lst : 각 테케마다 입력된 문자열을 저장할 문자열 타입 배열, 최대 1만으로 크기를 설정한다.
• Trie : 트라이를 구현할 구조체, 숫자열 문자를 받아오므로 child의 크기는 10으로 설정한다.

 

함수

1. insert

bool insert(Trie* node, const string& str)

 

1. 트라이에 새로운 전화번호를 넣는 함수
2. 전화번호를 넣는 도중 접두어가 있는지 체크까지 해주어야 한다.
3. 만약 접두어가 있다면 탐색을 그만하고 NO를 출력해 주어도 된다.

 

문제풀이

1. tc를 입력 받고 tc만큼의 테스트 케이스를 실행한다.
2. 각 테케마다 n을 입력 받고 root 트라이를 초기화 해준다.
3. n개의 전화번호를 문자열로 받아 lst배열에 저장해 준다.
4. lst배열을 오름차순으로 정렬해 준다.
5. 접두어가 존재하는지를 찾기 위해 flag를 사용해 준다, 초기값은 1로 세팅한다.
6. flag가 활성화 되있다면 오름차순된 lst배열을 순회하면서 각 인자를 트라이에 insert작업을 해준다.
7. insert는 반환값이 bool타입으로 flag의 값을 지속적으로 변경해 준다.
8. 만약 flag가 false가 되었다면 바로 break처리를 해준다.
9. flag가 true라면 YES를, false라면 NO를 출력해 준다.
10. 테스트 케이스가 종료될 때까지 위 작업을 반복해 준다.

 

참고 사항

정렬을 꼭 해주어야 하는 문제였다.

예를들어 

1
2
11
1

 

이런 테스트 케이스가 들어왔다면

정렬을 하지 않은 상태일 경우 첫번째로 11이 들어왔고 두번째로 1이 들어온 상태이다.

그렇다면 트라이 내에서는 1 -> 1에 isEnd가 true이고, 1에 isEnd가 true이므로 YES가 출력된다.

하지만 문제의 의도를 생각한다면 11을 누르기 위해 1을 누르는 순간 1로 전화가 갈것이다.

따라서 오름차순으로 정렬을 해주어야 데이터의 정합성에 문제가 없어진다.

 

 

정답 코드

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
int tc, n;
string lst[10000];

struct Trie {
	Trie* child[10];
	bool isEnd;
	Trie() {
		memset(child, 0, sizeof(child));
		isEnd = false;
	}
};

bool insert(Trie* node, const string& str) {
	Trie* cur = node;
	for (const char& ch : str) {
		int idx = ch - '0';
		if (cur->isEnd) return false;
		else if (!cur->child[idx]) cur->child[idx] = new Trie();
		cur = cur->child[idx];
	}
	cur->isEnd = true;
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> tc;
	while (tc--) {
		cin >> n;
		Trie* root = new Trie();

		for (int i = 0; i < n; i++) cin >> lst[i];
		sort(lst, lst + n);

		int flag = 1;
		for (int i = 0; i < n; i++) {
			if (flag) flag = insert(root, lst[i]);
			else break;
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}