[프로그래머스] 자동완성 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA

🖇️ 문제 링크

코딩테스트 연습 - [3차] 자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.

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

 

---

📝 문제 분석

세 단어를 오름차순으로 정렬했을 때

gone을 기준으로 한다면, gone은 위 문자열인 go와 "go" 두 글자가 같고, 아래 문자열인 "guild"와 "g" 한 글자가 같습니다.

gone을 특정하기 위해서는 아래, 위 중 중복되는 부분이 더 큰 "go"에서 "n"한 글자를 더 입력해야 합니다.

결국, 위아래 문자열과 중복되는 길이를 비교하고 그 중 최대값 + 1이 입력해야하는 문자수 입니다.

하지만 현재 문자열 전체가 중복된다면, + 1할 수 없으므로 자신의 문자열 길이가 정답이 됩니다.

 

---

⌨️ 코드

import java.util.Arrays;
class Solution {
    public int solution(String[] words) {
        int answer = 0;
        Arrays.sort(words);
        
        for (int i = 0; i < words.length; i++) {
            int max, pre = 0, post = 0;
            String s;
            for (int j = 0; j < words[i].length(); j++) {
                s = words[i].substring(0, j + 1);
                
                if (i != 0 && words[i - 1].length() > j && words[i - 1].startsWith(s)) 
                	pre = s.length();
                
                if (i != words.length - 1 && words[i + 1].length() > j && words[i + 1].startsWith(s))
                	post = s.length();
            }
            max = Math.max(pre, post);
                
            if(max != words[i].length())
                max++;
            answer += max;
        }
        
        return answer;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0