트라이

문제 7432번: 디스크 트리 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파 www.acmicpc.net 풀이 문자열, 트라이 [백준][C++] 14725: 개미굴 문제 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마 kantatatam.tistory.com 위의 문제와 같은 풀이로, vector에 넣을 string을 '\'로 나눠서 넣는다. 코드 #include #include #include #..

문제 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 풀이 문자열, 트라이 이전 트라이 문제와 달리 접두사를 챙길 필요가 없다. 그러므로 Trie 구조체의 멤버 변수를 map로 두어 특정 string이 어떤 자식 노드를 가리키는지만 저장해 둔다. Trie에 string을 입력할 때는, map에 입력되는 string이 있는지 확인하고 없다면 새로운 Trie를 생성하여 map에 현재 string과 같이 저장한다. 출력 때는, 노드의 깊이도 같이 인자로 넣어주어 "--"가 현재 깊이만큼 출력된 다음..

문제 16934번: 게임 닉네임 첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, www.acmicpc.net 풀이 문자열, 트라이 입력된 문자열의 접두사를 닉네임으로 사용할 수 있다면 해당 접두사를 출력하고, 사용할 수 없다면 이름에 이전에 입력된 이름의 수(1은 제외)를 붙여서 출력한다. 입력된 문자열(name)의 접두사(prefix)를 모두 탐색한다. 가능한 접두사 목록은 다음과 같다. [1, 1], [1, 2], [1, 3], ... , [1, N] 현재 trie에 입력된 문자열들 중에서 prefix를 접두사로 하는 문자열이 없다면 prefix를..

문제 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 풀이 문자열, 트라이 [백준][C++] 5052: 전화번호 목록 문제 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 kantatatam.tistory.com 위의 문제 처럼 트라이를 사용하는 문제다. 특정 ..

문제 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 문자열, 트라이 [Algorithm] 트라이(Trie) 개념과 기본 문제 Practice makes perfect! twpower.github.io 다른 풀이를 보면 여러 방법이 있는 것 같지만, 기본 트라이 문제라고 해서 트라이로 풀었다. 트라이 개념은 위의 링크로... 코드 #include #include #include using namespace std; const int MAX_NUM = 10; struct Trie {..