카카오 신입공채 3차 코딩테스트 문제5 자동완성 JAVA Tire구현

카카오 신입공채 3차 코딩테스트 문제5 자동완성 JAVA Tire구현

---

이 블로그를 만든 계기가 카카오 신입공채 코딩테스트의 문제 수준을 보고 깊은 자기반성의 끝에 블로그를 개설하고 알고리즘 문제를 풀어보고자 마음먹었습니다. 드디어 그 시작이자 마지막 문제인 자동완성 문제입니다. 문제설명은 다음과 같습니다.

각 문자를 리턴받기 위해서 몇번의 타이핑을 해야 하는지 구하는 문제입니다. 아래는 출력형식과 입출력 예제 입니다.

출처 : http://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/

카카오 자동완성 문제 JAVA 예제 

---

문제 해설을 보면 본 문제는 일반적인 스트링 비교로 풀게되면 테스트 케이스에서 타임오버가 나오게 됩니다. 우선 가장 심플하게(무식하게) 풀어본 스트링 비교로 풀어본 버젼입니다. 3중 for문 까지 쓰게 되었으니 최소 n^3의 시간복잡도를 갖게 될 것 같습니다. 그래도 우선 테스트 케이스의 결과는 정상적으로 출력됩니다.

자동완성 무식한 버젼

public static int count(String[] arr) {
    int keyConut = 0;
    int matchCount = 0;
    for(String key : arr) {
        String subKey;
        for(int i = 1 ; i <= key.length() ; i++) {
            subKey = key.substring(0, i);
            // subKey를 받아볼때마다 count++로 간주
            keyConut++;
            matchCount = 0;
            // subKey를 입력된 배열과 startWith로 검사하여 오직 한개가 나오는지 검사
            for(String target : arr) {
                if(target.startsWith(subKey)) {
                    matchCount++;
                }
            }
            // 검색결과가 한개가 나오면 다음문자로 넘어감
            if(matchCount == 1) {
                break;
            }
        }
    }
    return keyConut;
}

아무래도 마음이 편치 않아서 자동완성 문제를 Trie자료구조를 이용하여 구현해본 예제 입니다. 다른 분 소스를 조금 참고하려고 해도 대부분 다른 블로거 분들은 카카오 코딩테스트 1일차만 남기셔서 레퍼런스를 찾기 힘들어 직접 구현해 보았습니다.

자동완성 JAVA Trie구현 버젼

Trie를 선언하고 데이터 입력하고 count를 구하는 소스

public static int count(String[] arr) {
    // Trie 데이터 입력
    Trie trie=  new Trie();
    for(String str : arr) {
        trie.insert(str);
    }
    
    // 입력 데이터 별 카운트
    int count = 0;
    for(String str : arr) {
        for(int i = 1 ; i <= str.length() ; i++) {
            count++;
            String word = str.substring(0, i);
            
            // 한글자씩 늘려서 나오는 노드가 1개인 경우 더이상 진행하지 않음
            if(trie.findLeafs(word).size() == 1) {
                break;
            }
        }
    }
    
    return count;
}

아래는 Trie 자료구조를 구현한 소스

private static class Trie {
    TrieNode root;
    
    public Trie() {
        root = new TrieNode(' ');
    }
    
    /**
     * Trie에 문자열 입력
     * @param word
     */
    public void insert(String word) {
        TrieNode current = root;
        for(char c : word.toCharArray()) {
            if(current.getChild(c) != null) {
                current = current.getChild(c);
            }
            else {
                current = current.putChild(c);
            }
        }
        current.setLeaf(true);
    }
    
    /**
     * 문자열 word까지 입력된 경우 리턴되는 모든 leaf 리턴
     * @param word
     * @return
     */
    public ArrayList<TrieNode> findLeafs(String word) {
        ArrayList<TrieNode> retList = new ArrayList<TrieNode>();
        
        TrieNode current = root;
        
        //입력된 word에 해당하는 마지막 TrieNode를 탐색
        for(char c : word.toCharArray()) {
            if(current.getChild(c)!=null) {
                current = current.getChild(c);
            }
            else {
                retList.clear();
                return retList;
            }
        }
        
        // 마지막 TrieNode가 leaf이면 추가
        if(current.isLeaf()) {
            retList.add(current);
        }
        
        // 현재 TrieNode에 연결된 자식노드들의 모든 leaf를 추가
        retList.addAll(current.getAllLeaf());
        return retList;
    }
}
 
private static class TrieNode {
    private char data;
    private boolean isLeaf;
    private HashMap<Character, TrieNode> children;
    
    public TrieNode(char c) {
        this.data = c;
        children = new HashMap<Character, TrieNode>();
        isLeaf = false;
    }
    
    public HashMap<Character, TrieNode> getChildren() {
        return children;
    }
    
    public boolean isLeaf() {
        return isLeaf;
    }
    
    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }
    
    /**
     * 입력 c에 해당하는 TrieNode 생성 후 Child로 추가
     * @param c
     * @return
     */
    public TrieNode putChild(char c) {
        TrieNode temp = new TrieNode(c);
        getChildren().put(c, temp);
        return temp;
    }
    /**
     * 현재 노드의 자식노드 중 입력값 c에 해당하는 값 리턴
     * @param c
     * @return
     */
    public TrieNode getChild(char c) {
        return getChildren().get(c);
    }
    
    /**
     * 현재 노드와 연결된 모든 자식노드 중 leaf에 해당하는 노드 전부 리턴
     * @return
     */
    public ArrayList<TrieNode> getAllLeaf() {
        ArrayList<TrieNode> retList = new ArrayList<TrieNode>();
        for(TrieNode child : getChildren().values()) {
            if(child.isLeaf()) {
                retList.add(child);
            }
            retList.addAll(child.getAllLeaf());
        }
        return retList;
    }
    
}

이것으로 카카오 신입공채 코딩테스트 문제를 모두 정리해 보았습니다. 생각모두 엄청나게 난이도가 높은 문제들이 많았습니다. 연차만 쌓이고 실력은 늘지 않는 것 같아서 답답할 때가 많았는데 심심할때마다 알고리즘 푸는 것도 굉장히 재미있네요.