[java] 프로그래머스 - 자동완성

문제

프로그래머스-자동완성
주어진 문자열을 학습 후 순서대로 찾ㅇ르 때 몇개의 문자를 입력하면 되는지 계산하는 문제

• 제한사항
  학습과 검색에 사용될 중복 없는 단어 N : 2 <= N <= 100,000
  단어 길이의 총합 L : 2 <= L <= 1,000,000

풀이

단어검색?? 무족권 트라이트리다
트라이트리를 구현할 때 일반적인 구조는 아래와 같다

• 일반적인 구조

  class Node{
    Map<Character, Node> children = new HashMap<>();
    boolean isEnd;
  }
  

  children : 하위 글자를 담는 자료구조
  isEnd : 단어의 마지막 글자인지 아닌지 저장

• 풀이에 사용한 구조

  class Node{
    Map<Character, Node> children = new HashMap<>();
    int cnt;
  }
  

  이 문제에서 먼저 주어진 단어들로 학습을 하고, 그 단어들을 검색할 때 몇번의 입력을 해야하는지를 구해야 하기 때문에 cnt라는 변수를 만들었다
  또한 cnt의 값에 따라서 isEnd와 같은 역할을 하기 때문에 isEnd대신 cnt만 사용했다

문제에 나와있는 예시처럼 “go”, “gone”, “guild”가 있다면
각 단어를 저장할 때 cnt값을 증가시켜서 중복되는 횟수를 저장한다
모든 단어를 저장하고 난 후 노드의 값들은 그림과 같다

“go”를 검색할 때 루트노드에서 글자를 따라 내려가면서 글자 입력횟수를 추가하고 cnt == 1이면 종료한다
cnt == 1이라는 것은 해당 글자를 사용하는 단어가 1개라는 뜻이므로 이후 글자를 입력하지 않아도 된다는 뜻이다

• “go” 확인하기
  루트노드에서 [g -> o]를 찾아 내려가면서 글자 입력횟수를 추가한다
  • “g“를 입력(글자 입력 수 : 1)
    “g“로 시작하는 단어가 3개 있으므로 글자를 추가로 입력해야한다
  • “o“를 입력(글자 입력 수 : 2)
    “go”를 전부 입력했다
    = 총 입력 수 : 2

• “gone” 확인하기
  루트노드에서 [g -> o -> n -> e]를 찾아 내려가면서 글자 입력횟수를 추가한다
  • “g“를 입력(글자 입력 수 : 1)
    “g”로 시작하는 단어가 3개 있으므로 글자를 추가로 입력해야한다
  • “o“를 입력(글자 입력 수 : 2)
    “go”를 접미사로 갖는 단어가 2개 있으므로 글자를 추가로 입력해야한다
  • “n“을 입력(글자 입력 수 : 3)
    “gon”을 접미사로 갖는 단어가 1개 있으므로 글자를 추가로 입력할 필요가 없다
    = 총 입력 수 : 3

단어를 삽입하는 부분은 curr.cnt++를 추가했다

private void insert(Node curr, String str) {
	for (char c : str.toCharArray()) {
		curr = curr.children.computeIfAbsent(c, l -> new Node());
		curr.cnt++;
	}
}

소스코드

import java.util.*;
class Solution {
	static int answer;

	public int solution(String[] words) {
		answer = 0;
		Node root = new Node();
		for (int i = 0; i < words.length; i++) { // 단어 삽입
			insert(root, words[i]);
		}
		for (int i = 0; i < words.length; i++) { // 각 단어를 검색하는데 필요한 글자수 확인
			check(root, words[i]);
		}
		return answer;
	}
	// 각 단어를 검색하는데 필요한 글자수를 찾는 메서드
	private void check(Node curr, String target) {
		for (char c : target.toCharArray()) {
			curr = curr.children.get(c);
            answer++;
			if (curr.cnt == 1) {
				return;
			}
		}
	}
	// 트라이 자료구조에 단어를 추가하는 메서드
	private void insert(Node curr, String str) {
		for (char c : str.toCharArray()) {
			curr = curr.children.computeIfAbsent(c, l -> new Node());
            curr.cnt++;
		}
	}
}

class Node {
	Map<Character, Node> children;
	int cnt;

	public Node() {
		children = new HashMap<>();
	}
}