[programmers/kakao] [3차] 압축 (Java/Trie)

문제

출처 : https://programmers.co.kr/learn/courses/30/lessons/17684

코딩테스트 연습 - [3차] 압축

알파벳 'A' - 'Z'로 이루어진 사전과 문자열 msg가 주어진다.

이 msg의 문자중 사전과 최장 일치하는 문자를 찾고, 문자열이 일치하지않는다면, 사전에 추가하며, 일치하는 문자열의 Index(색인 번호)를 출력하는 문제다.

---

풀이

우선 이 문제에서 msg의 길이는 최대 1,000이다. 완전탐색으로 구현할 경우, 최악의 경우는 (아마)다음과 같을것 이다.

msg : "AAAAA...AAAAA" (A 1000개)

위 경우, 가장 오래걸리는 '사전 추가' 작업이 ((1000+1)*(1000/2))*1000번 반복한다. (실제로는 이 보다 적으나, 중요한 부분이 아니므로 러프하게 계산했음)

따라서, 시간복잡도의 경우, msg의 길이를 n이라 했을때, O(n^2*n/2) 이 되며, 완전탐색으로도 풀 수 있다.

 

하지만, 제목에 있듯이 나는 Trie로 풀었다.

Trie 자료구조에 익숙하다면, 구현에 따라 완전탐색과 비슷한 시간에 구현할 수 있으며, 시간복잡도 또한 극적으로 줄어든다.

하나의 단어를 추가할때, "일치하는 단어의 길이" 만큼 반복하므로 다음과 같은 (최악의 경우) 테스트 케이스에서,

msg : "AAAAA...AAAAA" (A 1000개)

하나의 단어를 추가할때, 1000번의 반복으로 추가 가능하다. 이 를 1000번 반복하므로, 최악의 경우 반복횟수는 1,000,000 이 된다.

따라서, 시간복잡도의 경우, msg의 길이를 n이라 했을때, O(n^2)이 된다.

 

알고리즘

1. Trie구조를 초기화한다. ('A'~'Z'를 각 인덱스 '1'~'26'으로 초기화 하며, Trie의 root에 연결시킨다.)

2. 단어에서 msg의 부분에 해당하는 단어를 찾을 수 없을때 까지 Trie자료구조를 타고 올라가며 탐색한다.

3. 찾을 수 없는 알파벳을 마지막 Trie구조에 연결시키며, 인덱스를 업데이트한다.

위 과정을 반복하면 된다.

 

Trie 구조 소스코드

class Trie{
    
    private char word;
    private int idx;
    private Trie[] nextTries;
    
    public Trie(char word, int idx){
        this.word = word;
        this.idx = idx;
        this.nextTries = new Trie[26];
    }
    
    public char getWord(){
        return this.word;
    }
    
    public void setNext(char c, int idx){
        if(this.hasNext(c)) return;
        this.nextTries[(int)c-(int)'A'] = new Trie(c, idx);
    }
    
    public Trie next(char c){
        return this.nextTries[(int)c-(int)'A'];
    }
    
    public boolean hasNext(char c){
        return this.nextTries[(int)c-(int)'A'] != null;
    }
    
    public int getIdx(){
        return this.idx;
    }
    
}

 

 

완전탐색으로 풀면 솔브드 랭크 실버1? 2? 정도 될거같고 트라이로 풀면, 골드 3? 2? 정도 될 것 같다.

 

 

---

전체 소스코드 

https://github.com/devxb/JJUNalgo/blob/master/%5B3%EC%B0%A8%5D%20%EC%95%95%EC%B6%95/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃