[BaekJoon Silver5] C++: 단어 정렬

Solved.ac Class2에 있는 단어 정렬에 대한 풀이 및 탐구에 대한 기록.

정답률 40.448%.

문제 분석

Input: 

• 단어의 개수 N
• 알파벳 소문자 단어 N개, 최대 길이 50.

Output: 

• 정렬한 단어들을 순서대로 출력.

길이가 짧은 것부터, 같으면 사전 순으로. 
단, 중복 단어는 하나만 남기고 제거.

문제 풀이

초안

소요시간: 23분 30초 : 다 풀고 조금 멍때렸다...

#include <iostream>

using namespace std;

struct Node {
public:
	string word;
	Node* left;
	Node* right;
	Node(const string& w) : word(w), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
private:
	Node* root;

	Node* insert(Node* node, const string& word) {
		if (node == nullptr) {
			return new Node(word);
		}

		if (word.size() < node->word.size()) {
			node->left = insert(node->left, word);
		}
		else if (word.size() > node->word.size()) {
			node->right = insert(node->right, word);
		}
		else {
			if (word < node->word) {
				node->left = insert(node->left, word);
			}
			else if (word > node->word) {
				node->right = insert(node->right, word);
			}
		}

		return node;
	}

	void inorder(Node* node) const {
		if (node == nullptr) return;
		inorder(node->left);
		cout << node->word << endl;
		inorder(node->right);
	}

	void destroyTree(Node* node) {
		if (node != nullptr) {
			destroyTree(node->left);
			destroyTree(node->right);
			delete node;
		}
	}
public:
	BinarySearchTree() : root(nullptr) {}

	void insert(const string& word) {
		root = insert(root, word);
	}

	void display() const {
		inorder(root);
	}

	~BinarySearchTree() {
		destroyTree(root);
	}
};

int main() {
	int wordCount;
	cin >> wordCount;


	BinarySearchTree bst;
	for (int i = 0; i < wordCount; i++) {
		string curWord;
		cin >> curWord;
		bst.insert(curWord);
	}

	bst.display();
}

 

느낀 점

set 라이브러리를 사용하면 조금 더 간단하게 문제를 풀 수 있었겠지만, 문득 이 문제를 본 순간 이진트리를 사용하면 수월하게 풀 수 있겠다는 생각이 들어 직접 이진탐색트리를 구현해보았다. 
insert할 때를 제외하곤 특정 단어를 찾을 필요가 없기 때문에 AVL트리나 레드-블랙 트리로 만들지는 않았다. 오랜만에 이진트리를 구현했지만 처음 배울 때랑 다르게 코드 자체는 간단해서 포인터의 개념을 이해하기 좋은 예제라는 생각이 들었다.