[프로그래머스] level 4 가사 검색(자바스크립트)

프로그래머스

---

👨‍💻 문제

---

정답 코드

답안 1(Map 활용)

답안 2

---

문제 풀이

 트라이(trie) 자료 구조를 활용하여 풀 수 있는 문제이다. 트라이는 '문자열을 찾거나 일치 여부를 판별하는 데' 유용한 자료 구조이다. 

 트라이는 중첩된 객체 구조로 되어 있다. 트라이의 삽입 메서드를 실행하면 문자열을 순회하며 탐색하는 문자가 root에 존재하지 않을 시 해당 문자를 key로 갖는 객체를 생성한다. 이러한 객체가 줄줄이 달려 트리를 형성하는 것이다. 'kang'과 'kim'이라는 문자열을 입력했을 시 아래와 같은 트라이 자료 구조가 생성된다.

const trie = {
    k: {
        a: {
            n: {
                g: {},
            },
        },
        i: {
            m: {},
        },
    },
};

 즉, k는 a와 i로 분기되고 각각 다음에 오는 문자를 다시 자식으로 갖는 구조를 반복하는 것이다.

 답안 2를 기준으로 설명하자면 위와 같이 문자열의 길이별로 트라이를 정방향과 역방향 각각 만들어야 한다. 물음표가 접두사로 등장한다면 문자열이 뒤에 와서 해당 문자열을 뒤에서부터 탐색해야 한다. 따라서 미리 문자열을 뒤집어 놓는 것이다. 주어진 words 배열을 for 반복문으로 탐색하여 trie를 생성하고, queries를 다시 탐색하면서 getSum 메서드를 실행한다. getSum 메서드는 탐색하는 문자가 ?라면 해당 깊이의 sum을 반환한다. 이 같은 반환값을 map 메서드를 활용하여 배열로 만들면 정답이다.

---

함께 보기

[자료 구조] 트라이(Trie)

프로그래머스

[프로그래머스] 60060 가사 검색 - 자바스크립트