Shortest Unique Prefixes 와 Trie 자료구조

거 참 오늘 문제 풀기 딱 좋은 날씨네~☀️

 

월요일 아침 아주 따끈한 문제가 도착했다.

사실 알고리즘이니 뭐니 별 관심이 없었는데 말야... 이게 참 한번 쳐다만 보게되도 뭐 거의 홀리는 수준으로 하루 종일 파고들게 된단 말이지.... 흠...요망한 것(👿).

 

문제: Shortest Unique Prefixes
Given a list of words, return the shortest unique prefix of each word. 

주어진 단어 목록에서 각 단어의 **최단 유일 접두사(Shortest unique prefix)를 찾아서 반환하시오.

예시:

[given the list]
dog
cat
apple
apricot
fish

[Return the list]
d
c
app
apr
f

 

우선 이 문제를 풀기 위해 알아둬야할 기본 개념!! Trie 자료구조(원래 알고 있었던 것처럼 자연스럽게 말하기!!!🤪)

 

Trie 자료구조

**Trie(트라이)**는 문자열을 효율적으로 다루는 자료구조로, 특히 접두사(prefix) 검색에 아주 강력한 성능을 자랑한다고 함.
여러 단어들이 같은 접두사를 공유할 때 유용하게 사용할 수 있다고 함.

Trie의 특징:

• 중복되는 접두사를 효율적으로 관리
• 단어의 삽입과 검색이 빠름
• 주로 자동완성, 사전에서 많이 활용

 

사실 처음 문제를 봤을 때 unique prefix라는 부분에 꽂혀서 "내가 그걸 어떻게 알어"라고 황당했었다.

아니~ 걔가 고유한지 안한지 내가 어케 암? 영문학적으로 뭐 접근해야 함? 이라는 생각을 했었지 ㅎㅎ

 

근데 주어진 단어 리스트에서 각 단어의 고유 접두사를 찾아내라는 말이었다.(고 내 친구 gpt가 친절하게 알려줬다~ 내 짱친~ 😘)

아니 왠지 영어로 문제를 읽으면 단순한게 단순해보이지 않는다는 말이지.. 나만 그래???

 

자, 위의 단어 리스트에서 각 단어의 고유한 접두사를 찾아보자면:

• "apple"과 "apricot"은 app까지 겹치므로, "apple"의 고유한 접두사는 app
• "cat"과 "dog"는 첫 글자가 다르므로, 각각 c와 d가 고유한 접두사
• "fish"는 앞에 다른 단어가 없으므로, 고유한 접두사는 f

이런 결론이 나온다.

 

Trie 구현(클래스 방식)

class TrieNode {
  constructor() {
    this.children = {};
    this.count = 0;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
      node.count++;
    }
  }

  getUniquePrefix(word) {
    let node = this.root;
    let prefix = "";
    for (let char of word) {
      prefix += char;
      if (node.children[char].count === 1) {
        return prefix;
      }
      node = node.children[char];
    }
    return prefix;
  }
}

const words = ["dog", "cat", "apple", "apricot", "fish"];
const trie = new Trie();
words.forEach(word => trie.insert(word));

const result = words.map(word => trie.getUniquePrefix(word));
console.log(result);  // ["d", "c", "app", "apr", "f"]

 

설명:

1. 각 단어를 Trie에 삽입하면서 각 노드의 count를 증가시킴
2. 고유한 접두사를 찾을 때, 해당 접두사의 count가 1일 경우, 고유한 접두사로 판단하여 반환

 

즉, inset("dog")를 하면:

 

1. root에서 'd' 없으면 {d: {}} 추가
2. 'd'안에서 'o' 없으면 {o:{}} 추가
3. 'o'안에서 'g' 없으면 {g:{}} 추가

 

{
  d: {
    count: 1,
    o: {
      count: 1,
      g: {
        count: 1
      }
    }
  }
}

 

이런 구조가 됨. 흠... 너무 복잡하지 않나...?? 

이 방식은 효율적이지만, 구현이 다소 복잡하고 메모리 사용량이 많을 수 있다.

 

 

 

정렬과 비교로 해결!!

Trie 대신 정렬과 비교로도 찾을 수가 있다.

function shortestUniquePrefixes(words) {
  words.sort(); // 단어 리스트 정렬

  const result = [];

  for (let i = 0; i < words.length; i++) {
    const word = words[i];
    const prev = words[i - 1] || ""; // 이전 단어
    const next = words[i + 1] || ""; // 다음 단어

    let prefix = "";

	// 접두사 확인
    for (let j = 0; j < word.length; j++) {
      prefix += word[j];

      // 앞 단어, 뒷 단어 둘 다 현재 prefix로 시작하지 않으면 유일한 접두사
      if (!prev.startsWith(prefix) && !next.startsWith(prefix)) {
        break;
      }
    }

    result.push(prefix);
  }

  return result;
}

// 예시 단어 리스트
const words = ["dog", "cat", "apple", "apricot", "fish"];
console.log(shortestUniquePrefixes(words)); // ["d", "c", "app", "apr", "f"]

 

헤헷~ 코드가 좀 깔끔해진 것같은 느낌적인 느낌

 

설명:

1. 단어 리스트를 정렬한 후, 각 단어를 앞과 뒤의 단어와 비교하여 고유한 접두사를 찾는다.
2. 정렬된 리스트에서 각 단어는 앞뒤 단어와 비교하여 고유한 접두사를 쉽게 확인할 수있다.

 

 

방법	장점	단점
Trie	- 빠른 검색 - 메모리 효율적 - 자동완성 등 실시간 검색에 유리	- 구현이 복잡함 - 메모리 많이 사용
정렬+비교	- 간단하고 빠르게 구현 가능 - 소규모 데이터에 적합	- 데이터 양이 많을 때 비효율적

 

결론

• Trie는 접두사를 빠르게 검색하고 중복되는 부분을 효율적으로 처리하는 강력한 자료구조이다.
• 작고 간단한 문제라면 정렬과 비교 방법도 좋은 해결책이 될 수 있다.
• 상황에 맞는 자료 구조를 선택하는 것이 중요하다.

 

하핫~ 오늘은 월요일이어서 마무리 멘트가 생각이 안남.

그럼 이만🤚🏻