햄랑

공부했던 것들을 남기는 곳입니다:)

프로그래머스: [3차] 자동완성⭐⭐⭐⭐

업데이트:     Updated:

카테고리:

태그: , , ,

체감 난이도 : ⭐⭐⭐
유형 : 트라이

문제 🧐

문제 설명

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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 result
[“go”,”gone”,”guild”] 7
[“abc”,”def”,”ghi”,”jklm”] 4
[“word”,”war”,”warrior”,”world”] 15

입출력 설명

  • 첫 번째 예제는 본문 설명과 같다.
  • 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
  • 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
    • word는 word모두 입력해야 한다.
    • war는 war 까지 모두 입력해야 한다.
    • warrior는 warr 까지만 입력하면 된다.
    • world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)

✏️ 첫번째 풀이(실패)

#include <bits/stdc++.h>

using namespace std;

int answer = 0;

class trie {
    public:
    trie* alpha[26]; // 다음 철자에 해당하는 노드를 가리키는 포인터
    bool checked; // 단어 완성 체크 변수
    int cnt; // 몇개의 단어가 해당 노드를 경유하는가?

    trie() {
        // 다음 노드 포인터 초기화
        for(int i=0; i<26; i++) {
            alpha[i] = nullptr;
        }

        // 현재 노드 변수 초기화
        checked = false;
        cnt = 0;
    }

    void init(vector<string> words) {
        for(string word : words) {
            add_word(word, 0);
        }
    }

    // 트라이에 단어 추가
    // string word를 string& word로만 바꿔줘도, 이 문제가 풀린다.
    void add_word(string word, int ind) {

        int c = word[ind] - 'a';
        // 철자에 해당하는 다음 노드가 비어있으면,
        // 노드 동적 생성
        if(alpha[c] == nullptr)
            alpha[c] = new trie();

        // 다음 노드 카운트 업
        alpha[c]->cnt++;

        // 단어의 마지막 철자라면,
        // 체크 후, 종료
        if(word.size()-1 == ind) {
            alpha[c]->checked = true;
            return;
        }

        // 다음 철자 추가
        alpha[c]->add_word(word, ind+1);   
    }

    // 순회하며 입력 횟수 계산
    void traverse() {
        for(int i=0; i<26; i++) {
            if(alpha[i] != nullptr) {

                answer += alpha[i]->cnt;

                if(alpha[i]->cnt==1) {
                    continue;
                }

                alpha[i]->traverse();

            }
        }
    }
};

int solution(vector<string> words) {
    trie t;
    t.init(words);
    t.traverse();

    return answer;
}

가장 마지막 테스트 케이스에서 시간초과가 나며 95.5/100점으로 실패했다.

왜 시간이 많이 걸렸나 알아본 결과는 다음과 같다.

  1. 총 단어의 길이만큼 동적 할당을 계속해주어야 한다.
  2. add_word를 호출할 때 문자열 복사가 일어난다.

처음에는 add_word에 가장 큰 문제가 있다는 사실을 알지 못하고,
alpha[26] 배열을 unordered_map 형태로 바꾸거나, 미리 Trie 객체들을 생성해두는 시도를 했다.

아래가 미리 Trie 객체 생성을 시도한 코드이다.

✏️ 두번째 풀이(성공)

#include <bits/stdc++.h>
using namespace std;

class Trie {
public:

  Trie* alpha[26];
  bool checked;
  unsigned long long cnt;

  Trie() {
    for(int i=0; i<26; i++) {
      alpha[i] = nullptr;
    }
    checked = false;
    cnt = 0;
  }

  void insert(const char* str);
  int find(const char* str, unsigned long long cnt);
};

int NodeIndex = 1; // 다음으로 할당할 NodePool 인덱스
Trie NodePool[1000010];

void Trie::insert(const char* str) {
  if(*str == '\0') {
      checked = true;
      return;
  }
    
  int c = *str - 'a';
  if(alpha[c] == nullptr) {
    alpha[c] = &NodePool[NodeIndex++];
  }
  
  alpha[c]->cnt++;
  alpha[c]->insert(str+1);
}

int Trie::find(const char* str, unsigned long long cnt) {
  if(*str == '\0') return cnt;
  int c = *str - 'a';
  
  if(alpha[c]->cnt == 1)
    return cnt+1;
  
  return alpha[c]->find(str+1, cnt+1);
}

int solution(vector<string> words) {
  unsigned long long answer = 0;
  
  // NodePool의 0번 인덱스를 루트로 잡았다.
  for(string word : words) {
    NodePool[0].insert(word.c_str());
  }
  
  for(string word: words) {
    answer += NodePool[0].find(word.c_str(), 0);
  }
    
  return answer;
}

어떻게 하면 시간초과를 막을수 있을까.. 고민하다가, 결국 다른 사람의 풀이를 보았다.

미리 배열을 통해 노트 풀을 생성해두는 방식을 사용하였다.

✔️ 다른 사람의 풀이

#include <string>
#include <vector>

using namespace std;

struct TRIE {
	TRIE *Node[26];
	int Child;
	bool Finish;

	void Insert(const char *Str);
	int Find(const char *Str, int Cnt);
};

int Trie_Idx;
TRIE Nodepool[1000010];

TRIE *Nodeset() {
	TRIE *NewNode = &Nodepool[Trie_Idx++];
	for (int i = 0; i < 26; i++) NewNode->Node[i] = NULL;
	NewNode->Child = 0;
  
	return NewNode;
}

void TRIE::Insert(const char *Str) {
	Child++;
	if (*Str == NULL) {
		Finish = true;
		return;
	}

	int Cur = *Str - 'a';
	if (Node[Cur] == NULL) Node[Cur] = Nodeset();
	Node[Cur]->Insert(Str + 1);
}
int TRIE::Find(const char *Str, int Cnt) {
	if (Child == 1 || *Str == NULL) return Cnt;

	int Cur = *Str - 'a';
	return Node[Cur]->Find(Str + 1, Cnt + 1);
}
int solution(vector<string> words) {
	Trie_Idx = 0;
	int answer = 0;
	int N = words.size();
	TRIE *Root = Nodeset();
	for (int i = 0; i < N; i++) Root->Insert(words[i].c_str());
	for (int i = 0; i < N; i++) answer = answer + Root->Find(words[i].c_str(), 0);
	
  return answer;
}

// 출처: https://yabmoons.tistory.com/490 [얍문's Coding World..:티스토리]

🧐 분석

이 분의 풀이를 보며, 두번째 풀이를 시작하였다.

  1. Nodeset 함수를 통해 새로운 노드를 초기화하고, 노드 포인터를 할당해준다.
  2. Find 함수와 Insert 함수로 분리한다.
  3. 트라이 배열을 미리 선언해두었다.
  4. 코드 가독성이 매우 높다.

이러한 점들이 매우 인상깊으며, 배울 점이 정말 많은 코드였다!

하지만 어느 상황에서든, 1000010개의 트라이 노드가 생성된다는 점은 아쉬웠다.

공간 복잡도 면에서는 동적 할당이,
시간 복잡도 면에서는 미리 배열로 할당하는 방법이 유리하기 때문이다.

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

참고