#include #include #include #include using namespace std; // 트라이 노드를 나타내는 구조체 struct TrieNode { TrieNode* children[10]; // 0~9까지의 숫자에 대응하는 10개의 자식 노드 배열 bool isEndOfWord; // 숫자 끝을 나타내는 플래그 // 생성자 TrieNode() { isEndOfWord = false; for (int i = 0; i < 10; ++i) { children[i] = nullptr; // 자식 노드는 처음에 null로 초기화 } } }; // 트라이 클래스 class Trie { public: TrieNode* root; // 트리의 루트 노드 // 생성자 Trie() { root = new TrieNode(); } // 숫자 문자열 삽입 함수 bool insert(const string& number) { TrieNode* node = root; for (int i = 0; i < number.length(); ++i) { int index = number[i] - '0'; // 숫자를 0~9로 변환 // 자식 노드가 없으면 새로 생성 if (node->children[index] == nullptr) { node->children[index] = new TrieNode(); } node = node->children[index]; // 현재 노드가 숫자의 끝을 나타내는데, 이 숫자 뒤로 추가적인 자식이 있으면 // 다른 숫자가 현재 숫자의 접두어가 됨 if (node->isEndOfWord && i != number.length() - 1) { return false; // 다른 숫자가 현재 숫자의 접두어가 됨 } } // 숫자가 끝까지 탐색되면 단어 끝을 표시 if (node->isEndOfWord) { return false; // 이미 이 숫자가 존재하는 경우, 완전한 중복 } node->isEndOfWord = true; // 숫자 끝을 true로 설정 return true; } // 접두어 관계가 있는지 확인 bool hasPrefixConflict(const string& number) { TrieNode* node = root; for (int i = 0; i < number.length(); ++i) { int index = number[i] - '0'; // 숫자를 0~9로 변환 if (node->children[index] == nullptr) { return false; // 해당 숫자에 대한 자식이 없으면 접두어 관계가 없음 } node = node->children[index]; } // 현재 위치에서 자식 노드가 더 있다면 이 숫자는 다른 숫자의 접두어 for (int i = 0; i < 10; ++i) { if (node->children[i] != nullptr) { return true; // 자식 노드가 있으면 접두어 관계 } } return false; // 자식 노드가 없으면 접두어 관계가 아님 } }; int main() { Trie trie; int t; cin>>t; while(t--){ bool f=true; int n; cin>>n; string c[10101]; for(int i=0;i>c[i]; } sort(c,c+n); for(int i=0;i

제출 #136802

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: