가장 긴 공통 접두사
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 10번째.
다음 챌린지들은 Trie를 사용하도록 설계되었습니다.
이전 레슨에서 만든 Trie와 TrieNode 클래스를 사용하세요 (왼쪽 파일에 제공되어 있습니다). 각 챌린지는 Trie를 사용하는 함수를 작성할 수 있는 새로운 solution 파일을 제공합니다.
첫 번째 문제: 단어 리스트가 주어졌을 때, 모든 단어가 공유하는 가장 긴 공통 접두사(longest common prefix)를 찾으세요. 모든 단어를 트라이(trie)에 삽입한 후, 정답은 각 단계에서 정확히 하나의 자식 노드만 존재하고 어떤 노드도 단어의 끝(end-of-word)이 아닐 때까지 루트에서 아래로 내려가는 경로입니다.
챌린지
쉬움문자열 배열 words를 입력받아 배열 내 모든 문자열의 공통 접두사 중 가장 긴 문자열을 반환하는 longestCommonPrefix 함수를 작성하세요.
배열이 비어 있거나 공통 접두사가 존재하지 않는 경우, 빈 문자열을 반환합니다.
반드시 Trie 클래스(trienode와 함께 trie에 제공됨)를 사용해야 하며, 개수를 세거나 추적하기 위해 언어 내장 기능인 set, dict, map 등을 사용해서는 안 됩니다.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestCommonPrefix(words, n);
printf("%s\n", res);
free(res);
return 0;
}