가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.
입력 형식
입력은 조건의 개수를 나타내는 정수n과n개의 원소로 구성된 문자열 배열data로 주어진다.data의 원소는 각 프렌즈가 원하는 조건이N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.
1 <= n <= 100
data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다.{A, C, F, J, M, N, R, T}각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
두 번째 글자는 항상~이다.
네 번째 글자는 다음 3개 중 하나이다.{=, <, >}각각 같음, 미만, 초과를 의미한다.
다섯 번째 글자는0이상6이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.
출력 형식
모든 조건을 만족하는 경우의 수를 리턴한다.
예제 입출력
ndataanswer
2
["N~F=0", "R~T>2"]
3648
2
["M~C<2", "C~M>1"]
0
예제에 대한 설명
첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.
두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.
접근 방법
백트래킹 기법을 사용하여 해결할 수 있었습니다.
1. 백트래킹을 사용하여 8명이 서있을 수 있는 모든 경우의 수에 대한 순열을 구합니다. (이 문제의 경우 8!개)
2. 구해진 한 조합에 대해 각각의 프렌즈 들이 원하는 조건(data)가 전부 만족하는지 확인합니다.
3. 한 조건에 대해 검사를 하는 방법은 아래와 같습니다.
3-1. 조건의 0번째 인덱스와 2번째 인덱스인 두 명과, 3번째 인덱스인 오퍼레이션(<, >, =) 마지막으로 4번째 인덱스인 오퍼레이션에 대한 수를 parsing합니다.
프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.
그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.
후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.
관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.
위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다. 그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다. 물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다. 따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.
릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.
제한사항
relation은 2차원 문자열 배열이다.
relation의 컬럼(column)의 길이는1이상8이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
relation의 로우(row)의 길이는1이상20이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
relation의 모든 문자열의 길이는1이상8이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
데이터 처리 전문가가 되고 싶은"어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
제한사항
s의 길이는 1 이상 1,000 이하입니다.
s는 알파벳 소문자로만 이루어져 있습니다.
입출력 예
sresult
"aabbaccc"
7
"ababcdcdababcdcd"
9
"abcabcdede"
8
"abcabcabcabcdededededede"
14
"xababcdcdababcdcd"
17
입출력 예에 대한 설명
입출력 예 #1
문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #2
문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #3
문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #4
문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다. 문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다. 문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다. 문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.
입출력 예 #5
문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
레스토랑을 운영하던스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.
예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)
손님 번호주문한 단품메뉴 조합
1번 손님
A, B, C, F, G
2번 손님
A, C
3번 손님
C, D, E
4번 손님
A, C, D, E
5번 손님
B, C, F, G
6번 손님
A, C, D, E, H
가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.
코스 종류메뉴 구성설명
요리 2개 코스
A, C
1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스
C, D, E
3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스
B, C, F, G
1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스
A, C, D, E
4번, 6번 손님으로부터 총 2번 주문됐습니다.
[문제]
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가추가하고 싶어하는코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
orders 배열의 크기는 2 이상 20 이하입니다.
orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
각 문자열은 알파벳 대문자로만 이루어져 있습니다.
각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
course 배열의 크기는 1 이상 10 이하입니다.
course 배열의 각 원소는 2 이상 10 이하인 자연수가오름차순으로 정렬되어 있습니다.
course 배열에는 같은 값이 중복해서 들어있지 않습니다.
정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로오름차순정렬해서 return 해주세요.
배열의 각 원소에 저장된 문자열 또한 알파벳오름차순으로 정렬되어야 합니다.
만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.
[입출력 예]
orderscourseresult
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]
[2,3,4]
["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]
[2,3,5]
["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]
[2,3,4]
["WX", "XY"]
입출력 예에 대한 설명
입출력 예 #1 문제의 예시와 같습니다.
입출력 예 #2 AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다. 요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.
입출력 예 #3 WX가 두 번, XY가 두 번 주문됐습니다. 3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다. 또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.
접근 방법
HashMap과 backTracking을 적절히 활용하여 해결할 수 있는 문제였습니다.
1. 문제를 해결하기에 앞서 orders를 정렬 해야합니다. 한 예시로 xy와 yx는 같은 조합으로 볼 수 있고, 이러한 경우를 수월하게 계산하기 위해 사전순으로 정렬합니다.
2. 최소 2번 이상 주문된 음식의 조합(backTracking)을 HashMap에 저장합니다. (HashMap<String 음식조합, Integer 주문횟수>)
3. HashMap의 원소를 각각 탐색하면서 음식조합의 수가 course의 한 요소와 일치한다면 가장 많이 주문된 횟수를 비교 갱신하며 음식조합 또한 추가 혹은 갱신을 합니다. 이 때 아래 2개의 HashMap을 사용하였습니다.
(1) HashMap<Integer, ArrayList<String>> maxMap = new HashMap<Integer, ArrayList<String>>(); (2) HashMap<Integer, Integer> maxCnt = new HashMap<Integer, Integer>();
maxMap은 음식조합의 수(course)에 따른 음식조합을 저장합니다. 만약 한 음식 조합의 주문된 횟수가 최대 주문 횟수랑 일치하는 경우 요소를 추가해야 하기 때문에 value는 List의 형태를 가져야 합니다.
maxCnt는 음식조합의 수(course)에 따른 주문된 최대 횟수를 저장합니다.
자세한 내용은 아래 소스코드에 주석으로 설명하겠습니다.
소스 코드
import java.util.*;
import java.lang.*;
class Solution {
HashMap<String, Integer> map = new HashMap<String, Integer>();
HashMap<Integer, ArrayList<String>> maxMap = new HashMap<Integer, ArrayList<String>>();
HashMap<Integer, Integer> maxCnt = new HashMap<Integer, Integer>();
public void backTracking(int n, int cnt, int now, String order, String comb){
if(cnt == n){
if(map.containsKey(comb)){ //이미 주문된 적 있는 조합이라면
int orderCnt = map.get(comb);
map.put(comb, orderCnt + 1); // 주문횟수 1증가
}
else
map.put(comb, 1);
}
for(int i = now; i<order.length(); i++){
comb += order.charAt(i);
backTracking(n, cnt+1, i + 1, order, comb);
comb = comb.substring(0, comb.length() - 1);
}
}
public ArrayList<String> solve(String[] orders, int[] course){
ArrayList<String> ans = new ArrayList<String>();
//1번 과정, 수월한 풀이를 위해 문자열 사전순 정렬
for(int i=0;i<orders.length;i++){
char[] tmp = orders[i].toCharArray();
Arrays.sort(tmp);
orders[i] = new String(tmp);
}
//2번 과정, i번째 주문에 대해 ,j개(최소 2개) 이상의 조합을 구함
for(int i=0;i<orders.length;i++)
for(int j=2;j<=orders[i].length();j++)
backTracking(j,0,0,orders[i], "");
//course를 map에 미리 매핑시킴, 이후 course의 요소인지 판별하기에 쉽게 이용 가능
for(int i=0;i<course.length;i++){
maxMap.put(course[i], new ArrayList<String>());
maxCnt.put(course[i], 0);
}
//3번 과정
for(Map.Entry<String, Integer> elem : map.entrySet()){
String foods = elem.getKey();
int cnt = elem.getValue();
if(cnt >= 2){
if(maxMap.containsKey(foods.length())){ //course의 요소라면
if(maxCnt.get(foods.length()) == cnt){ //최대 주문 횟수와 일치한다면
maxMap.get(foods.length()).add(foods); //추가
}
else if(maxCnt.get(foods.length()) < cnt){ //최대 주문 횟수 보다 더 크다면
maxCnt.put(foods.length(), cnt); //최댓값 갱신
ArrayList<String> newOne = new ArrayList<String>(Arrays.asList(foods));
maxMap.put(foods.length(), newOne); //새롭게 갱신
}
}
}
}
//결과들을 ArrayList에 담는다.
for(ArrayList<String> elem : maxMap.values())
for(int i=0;i<elem.size();i++)
ans.add(elem.get(i));
//사전순 정렬
Collections.sort(ans);
return ans;
}
public String[] solution(String[] orders, int[] course) {
ArrayList<String> ans = solve(orders, course);
String[] answer = ans.toArray(new String[ans.size()]);
return answer;
}
}
포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어,go가 한 번 입력되었다면, 다음 사용자는g만 입력해도go를 추천해주므로o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
예를 들어, 학습된 단어들이 아래와 같을 때
go gone guild
go를 찾을 때go를 모두 입력해야 한다.
gone을 찾을 때gon까지 입력해야 한다. (gon이 입력되기 전까지는go인지gone인지 확신할 수 없다.)
guild를 찾을 때는gu까지만 입력하면guild가 완성된다.
이 경우 총 입력해야 할 문자의 수는7이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
입력 형식
학습과 검색에 사용될 중복 없는 단어N개가 주어진다. 모든 단어는 알파벳 소문자로 구성되며 단어의 수N과 단어들의 길이의 총합L의 범위는 다음과 같다.
2 <=N<= 100,000
2 <=L<= 1,000,000
출력 형식
단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.
입출력 예제
wordsresult
["go","gone","guild"]
7
["abc","def","ghi","jklm"]
4
["word","war","warrior","world"]
15
입출력 설명
첫 번째 예제는 본문 설명과 같다.
두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
세 번째 예제는 총15자를 입력해야 하고 설명은 아래와 같다.
word는word모두 입력해야 한다.
war는war까지 모두 입력해야 한다.
warrior는warr까지만 입력하면 된다.
world는worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)
접근 방법
Trie 자료구조를 공부해봤다면 문제를 봤을 때 Trie를 사용해 해결할 수 있다는 것을 바로 떠올릴 수 있었을 것입니다.
저는 문제를 풀기 위해 Trie의 한 노드가 가지는 자료를 3가지를 정의하였습니다.
1. child HashMap<Character, Node> child = new HashMap();
2. boolean isEnd;
3. int branchSum;
1번 child는 노드의 child노드를 연결하기 위한 링크 역할을 합니다.
2번 isEnd는 단어의 끝인지의 여부를 나타냅니다.
3번 branchSum은 뻗어있는 가지의 수를 의미합니다. (isEnd == true)인 구간, 즉 단어의 끝을 가지는 부분도 하나의 가지로 계산합니다.
만약 단어가 go, gone, guild가 주어진다면 branchSum의 상태는 아래의 그림과 같습니다.
아래와 같은 코드로 branchSum을 계산할 수 있습니다.
public int makeBranchSum(Node now){
if(now.isEnd && now.child.isEmpty()) //단어의 끝이면서 더 나아갈 깊이가 없는 경우
return now.branchSum = 1;
for(Node node : now.child.values())
now.branchSum += makeBranchSum(node);
//단어의 끝이지만 더 나아갈 깊이가 있는 경우, 위 그림에서 노드(o)에 해당
if(now.isEnd && !now.child.isEmpty())
now.branchSum += 1;
return now.branchSum;
}
isEnd와 branchSum을 적절히 활용하면 문제를 해결할 수 있습니다.
1. 일단 처음으로 (branchSum == 1)인 구간에 도달한다면 더 이상의 가지가 뻗어있지 않다는 의미가 되므로 그 구간까지의 깊이를 반환하고, 더 깊은 곳으로 진입하지 않습니다.
2. 만약 branchSum != 1이고 isEnd == true인 경우면 더 나아갈 수 있는 가지는 남아있으나, 여기가 어떠한 단어의 끝이라는 의미가 되므로 그 구간까지의 깊이를 포함하여 더해줍니다.
public int search(Node now, int cnt){ //cnt는 깊이를 의미
int ret = 0;
if(now.branchSum == 1) //1번 항목 검사
return cnt;
for(Node node : now.child.values())
ret += search(node, cnt + 1);
if(now.isEnd) //2번 항목 검사
ret += cnt;
return ret;
}
소스 코드
import java.util.*;
class Solution {
public class Node {
HashMap<Character, Node> child = new HashMap();
boolean isEnd = false;
int branchSum = 0;
}
public class Trie {
Node root;
public Trie(){
root = new Node();
}
public void insert(String word){
Node current = root;
for(Character c : word.toCharArray()){
if(current.child.get(c) == null){
Node node = new Node();
current.child.put(c, node);
current = node;
}
else
current = current.child.get(c);
}
current.isEnd = true;
}
}
public int makeBranchSum(Node now){
if(now.isEnd && now.child.isEmpty())
return now.branchSum = 1;
for(Node node : now.child.values())
now.branchSum += makeBranchSum(node);
if(now.isEnd && !now.child.isEmpty())
now.branchSum += 1;
return now.branchSum;
}
public int search(Node now, int cnt){
int ret = 0;
if(now.branchSum == 1)
return cnt;
for(Node node : now.child.values())
ret += search(node, cnt + 1);
if(now.isEnd)
ret += cnt;
return ret;
}
public int solve(String[] words){
Trie trie = new Trie();
for(int i=0;i<words.length;i++){
String word = words[i];
trie.insert(word);
}
makeBranchSum(trie.root);
return search(trie.root, 0);
}
public int solution(String[] words) {
int answer = 0;
return answer = solve(words);
}
}
