[P4] 백준 5670번 휴대폰 자판 C++ 트라이, 메모리 풀

리뷰

 

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

구현까지는 금방 했지만 메모리풀을 구현하지 않아 틀린 문제

메모리 풀의 크기를 메모리 제한에 맞게 적당히 설정하였더니 AC를 받았다.

 

 

전역 변수

• n : 단어의 개수를 저장할 변수
• idx : 할당한 메모리 풀의 개수를 저장할 변수
• Trie : 트라이를 구현하기 위한 구조체, 트라이 배열 child와 배열 내 null이 아닌 크기 cnt를 갖는다.
• memory : 메모리 풀을 구현하기 위한 Trie 주소값 타입의 배열
• lst : 주어진 단어를 저장하기 위한 문자열 배열

 

함수

1. insert

void insert(Trie* root, const string& str)

 

트라이에 단어를 삽입하기 위한 함수

1. 매개변수로 Trie의 루트 주소값과 삽입할 문자열을 전달 받는다.
2. Trie의 주소값 cur을 root로 초기화 한다.
3. 문자열을 순회하며 현재 트라이에 해당 문자가 존재하지 않으면 트라이를 생성하고 메모리풀에 정의한다.
4. 현재 트라이 노드를 다음 노드로 이동하고 이동한 노드의 cnt를 증가시킨다.

 

2. query

int query(Trie* root, const string& str)

 

단어가 몇번의 버튼 입력으로 완성되는지를 확인할 함수

1. 매개변수로 Trie의 루트 주소값과 탐색할 문자열을 전달 받는다.
2. 정수형 변수 result를 1로 초기화 한다.
3. Trie의 주소값 cur을 root의 단어의 첫번째 문자 노드로 초기화 한다.
4. 정수형 변수 cnt를 현재 노드의 cntg값으로 초기화 한다.
5. 단어의 두번째 문자부터 순회하며 노드의 이동을 진행한다.
6. 만약 이전 노드의 cnt와 현재 노드의 cnt가 다르다면 result를 증가시키고 cnt를 현재 cnt값으로 변경한다.
7. 탐색을 마친 후 result에 저장된 값을 리턴해 준다.

 

문제풀이

1. 매 테스트 케이스 마다 n을 입력받는다.
2. idx를 0으로 초기화 해준다, 메모리 풀의 첫번째 인덱스를 Trie의 root로 초기화 한다.
3. n개의 단어를 lst배열에 입력 받고, insert함수를 통해 단어를 트라이에 삽입해 준다.
4. 정수형 변수 total을 0으로 초기화 한다.
5. n개의 단어를 순회하며 query함수에 전달하여 받은 리턴값을 total에 더해준다.
6. total / n을 소숫점 2자리 까지 반올림하여 출력해 준다.
7. memory배열을 0에서 idx까지 delete를 통해 사용한 메모리를 해제해 준다.

 

트러블 슈팅

1. 디버깅용 출력문을 제거하지 않고 제출하여 Fail을 받았다.
2. n의 최대 값이 10^5인데 lst배열의 크기를 10^4로 설정하여 Segfault를 받았다.
3. 메모리풀을 구현하지 않고 제출하여 메모리 초과를 받았다.
4. 메모리풀의 크기를 111111로 설정하였다가 OutOfBounds를 받았다.
5. 메모리풀의 크기를 55555로 설정하니 AC를 받았다.

 

참고 사항

• 현재 노드와 이전 노드의 cnt값이 다르다는 것을 자동완성이 끊기는 시점으로 인지하였다.

 

정답 코드

#include<iostream>
#include<cstring>
using namespace std;

int n, idx;
struct Trie {
	Trie* child[26];
	int cnt;
	Trie() {
		memset(child, 0, sizeof(child));
		cnt = 0;
	}
};
Trie* memory[555555];
string lst[100000];

void insert(Trie* root, const string& str) {
	Trie* cur = root;
	for (const char& ch : str) {
		int index = ch - 'a';
		if (!cur->child[index]) cur->child[index] = memory[idx++] = new Trie();
		cur = cur->child[index];
		cur->cnt++;
	}
}

int query(Trie* root, const string& str) {
	int result = 1;
	Trie* cur = root->child[str[0] - 'a'];
	int cnt = cur->cnt;
	for (int i = 1; i < str.size(); ++i) {
		int index = str[i] - 'a';
		cur = cur->child[index];
		if (cnt != cur->cnt) {
			result++;
			cnt = cur->cnt;
		}
	}
	return result;
}

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

	while (cin >> n) {
		idx = 0;
		Trie* root = memory[idx++] = new Trie();
		for (int i = 0; i < n; ++i) {
			cin >> lst[i];
			insert(root, lst[i]);
		}

		int total = 0;
		for (int i = 0; i < n; ++i) {
			total += query(root, lst[i]);
		}
		printf("%.2f\n", (double)total / n);

		for (int i = 0; i < idx; ++i) delete memory[i];
	}
}