넘치게 채우기

https://www.acmicpc.net/problem/1141BOJ - 접두사문제 유형: 트라이, 정렬, 그리디문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오. 입력첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 ..

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/description/?envType=daily-question&envId=2024-10-25leetcode - Remove Sub-Folders from the Filesystem문제 유형: 문자열 처리, 그리디, 트라이(Trie)문제 난이도: Medium 문제Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.If a folder[i] is located within another fo..

https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix/description/?envType=daily-question&envId=2024-09-24leetcode - Find the Length of the Longest Common Prefix문제 유형 : 트라이(Trie), 문자열 처리, 해시문제 난이도 : Medium 문제You are given two arrays with positive integers arr1 and arr2.A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmos..

트라이란? 트라이는 문자열의 저장과 탐색을 효율적으로 하기 위한 k진 탐색 트리이다. 단어들이 공동으로 가지는 접두사들을 이용해서 문자열을 저장하고 탐색한다. 트라이의 특징 1. 트라이의 루트에는 빈 문자열을 나타내는 노드부터 시작한다. 루트 노드부서 시작해서 문자열의 접두사부터 따라가기 시작한다. 2. 각 노드는 문자와 자식 노드에 대한 포인터를 가지고 있다. 3. 종료 노드는 해당 문자열이 Trie에 존재함을 나타낸다. 4. 문자열 검색은 루트에서 시작하여 해당 문자열의 모든 문자를 따라 이동한다.(문자열의 접두사를 얻을 수 있다) 트라이의 시간복잡도는 O(n)(문자열의 길이만큼) 이다.트라이는 검색이나 사전 등에서 사용된다. 각 노드는 다음 자손의 포인터와 nil을 모두 포함하는 배열을 가지고 있다..