[2018 KAKAO BLIND RECRUITMENT][3차] 자동 완성 for JAVA

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

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

[2020 KAKAO BLIND RECRUITMENT][1차]  for JAVA

 

[문제 설명]

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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

출력 형식

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

 

[풀이]

먼저 words 배열을 정렬한 뒤, HashMap에 인덱스와 문자를 넣어준다.

그리고 하나의 문자에 대해 위, 아래 문자를 비교하면 어느 정도 단어가 차이 나는지 알 수 있는데, 겹치는 부분이 있을수록 더 완성된 문자를 쳐야 되는 것과 같으므로 같거나 타겟이 되는 단어의 길이가 끝날 때까지 비교하면 된다.

 

위처럼 gone을 검사할 때, go와는 3개, guild와는 2개가 차이나므로 가장 큰 3번을 리턴해주면 된다.

 

[코드]

public int solution(String[] words) {
        HashMap<Integer,String> hm = new HashMap<Integer, String>();
        int count = 0;
        Arrays.sort(words);
        
        for(int i = 0; i < words.length; i++) {                            //정렬
            hm.put(i, words[i]);
        }
        
        for(int i = 0; i <words.length; i++) {                            //Map에 인덱스와 문자열 삽입
            count += getFindCount(hm, i);
        }
        return count;
    }
    
    public int getFindCount(HashMap<Integer,String> hm, int idx) {
        if(idx == 0) {
            return getCloseFind(hm, idx, idx+1);                                                    //0일 때와
        }
        else if(idx == hm.size() -1) {                                                                //마지막 요소일때
            return getCloseFind(hm, idx, idx-1);
        }else {
            return Math.max(getCloseFind(hm, idx, idx-1),getCloseFind(hm, idx, idx+1));                //아래단어와 위 단어의 차이 중 큰 것을 택한다.
        }
    }
    
    public int getCloseFind(HashMap<Integer,String> hm, int idx, int targetIdx) {
        String self = hm.get(idx);
        String target = hm.get(targetIdx);
        
        int count = 0;
        for(int i = 0; i < self.length(); i++) {
            if(self.charAt(i) == target.charAt(i)) {
                count++;
            }else {
                count++;
                break;
            }
            if(i == target.length()-1) {                                //self가 작거나 target이 작거나인데, self가 더 작은 경우는 반복문 범위때문에 상관이 없다.
                count++;
                break;
            }
        }
        return count;
    }

테스트 케이스 통과

 

 

느낀 점: 처음에는 해당 문제를 Trie 구조를 이용해서 풀려고 했다. 하지만 뭔지 모르게 부분적인 테스트케이스 실패와 런타임 오류.. 아마 코드를 잘 못 짜서 스택오버플로우가 던져진 것 같다. 카카오 테크 블로그에 나와있는 해결방법을 이용해서 해결했다.