(JAVA) 백준 5670번 : 휴대폰 자판 --- [트라이]

www.acmicpc.net/problem/5670

5670번: 휴대폰 자판

 

안녕하세요.

 

이 문제는 트라이 알고리즘을 사용하는건데, 약간의 기출변형이 있어 고민이 필요한 문제입니다.

 

 

우선 단어들을 다 트라이에 넣고, (이 때 별도의 리스트에 단어들을 저장해둡니다. 그 이유는 이따 하나씩 꺼내면서 버튼 횟수를 확인해야하기 때문입니다.)

 

한 단어씩 리스트에서 탐색하며 버튼 횟수를 count 합니다.

 

 

버튼 횟수 count하는 방법은 contains 함수를 만들어서 해결했는데,

 

  1)  자식 노드의 개수가 2개 이상이거나

  2)  해당 문자가 어느 문자열의 마지막 글자인데, 이후에도 다른 글자들이 줄줄이 이어지는 다른 문자가 있는 경우

 

이 두 가지 경우에 버튼 누른 횟수를 count++ 해줬습니다.

 

 

예를들어,

 

hello

help

helpme

hope

 

가 있다면,

 

 

hello : h -> e -> l -> o

help : h -> e -> p

helpme : h -> e -> p -> m (help 다음 이어지는 문자 존재)

hope : h -> o -> p (h 다음 o와 e 두 개가 존재)

 

가 되겠죠?

 

 

 

더 자세한 사항이나 궁금하신 부분은 하단 소스코드를 참고해주시고,

질문 댓글도 남겨주시면 감사하겠습니다.

 

 

이상입니다.

감사합니다!

 

 

 

소스코드

---