https://school.programmers.co.kr/learn/courses/30/lessons/17685

2018 카카오톡 블라인드 테스트 문제이자 프로그래머스 LV4 문제이다

1트

import java.util.*;

class Solution {
    
    HashMap<String,Integer> map = new HashMap<>();
    
    public int solution(String[] words) {
        
        int answer = 0;
        
        //앞에서부터 글자들 map에다가 저장 => map의 크기가 1인 경우까지 입력해야된다!
        for(String word:words){
            
            String temp = "";
            for(int i=0;i<word.length();i++){
                
                temp += word.charAt(i);
                map.put(temp,map.getOrDefault(temp,0)+1);
            }
        }
        
        for(String word:words){
            
            int len = 1;
            String temp = word.substring(0,1);
            while(!temp.equals(word)&&map.get(temp)>1){
                temp += word.charAt(len++);
            }
            answer += len;
        }
        
        return answer;
    }
    
    
}

문제해결

1. Apple 이라는 단어를 예를 들어보겠다. A, Ap, App, Appl, Apple 를 각각 HashMap에다가 넣어주었다
2. 나중에 찾을 때 App까지는 숫자가 2이상이고 Appl이 1이라면 Appl 부터 자동완성이 가능하다

하지만…

메모리 초과 문제가 발생했다

총 단어 100,000개 각각 길이가 1,000,000 까지이므로 최대 100,000*1,000,000 = 100억 개의 단어가 HashMap에 들어가야 하고, 이는 메모리 초과 문제를 발생시킨다