[프로그래머스 - 구현] 자동완성 (for kakao)

카테고리	게시글 작성 날짜	게시글 최근 수정 날짜	작성자
Algorithm	2019-08-27 20:38	2022.02.26. 19:51	Dev.Yang

 

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.

효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

 

예를 들어, 학습된 단어들이 아래와 같을 때

 

go
gone
guild

 

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

 

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

---

📄 [구현] 자동완성 With C++ Source Code

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAX_LEN 26
// 모든 단어는 알파벳 소문자로 구성된다.
#define TO_NUMBER(X) X - 'a'

typedef struct TriNode {

	int count = 0;              // 현재의 학습 된 문자가 몇개인지 알려주는 변수
	bool terminate = false;     // 문자의 끝을 알려주는 변수
	TriNode * child[MAX_LEN];

	TriNode() {
		memset(child, 0, sizeof(child));
	}

	~TriNode() {
		for (auto & node : child) {
			if (node) { delete node; }
		}
	}

	void insert(const char * key) {
        
        // 마지막 문자인 경우를 표시한다.
		if (*key == 0) { this->terminate = true; }
		else {
            // 소문자를 인덱스로 변환한다.
			const int next = TO_NUMBER(*key);
            
            // 현재 문자가 생성되어 있지 않은 경우 새로운 문자 인덱스 트리를 생성한다.
			if (child[next] == NULL) { child[next] = new TriNode(); }
            
            // 문자의 수를 증가시켜주며 다음 문자를 바탕으로 인덱스 트리를 생성한다.
			child[next]->count++;
			child[next]->insert(key + 1);
		}
	}

	int find(const char * key, const int cnt) {

		const int next = TO_NUMBER(*key);

        /* 
            해당 문자가 끝 문자인 경우에는 그 하나 전 단어만 입력하면 되기 때문에 현재 입력에서            하나를 빼어준다.
        */
		if (*key == 0 || child[next] == NULL) { return cnt - 1; }
		
        /* 
            해당 문자로 이어지는 문자열이 없는 경우 탐색을 종료한다. 왜냐하면 해당 문자로 시작하는 
            문자는 완전 다른 트리에 속하므로 다른 문자로 보아야 하기 때문이다.
            (이부분이 이해가 되지 않아서 많이 시간을 낭비함.)
        */
		if (child[next]->count == 1) { return cnt; }

		return child[next]->find(key + 1, cnt + 1);
	}

} Tri;

int solution(vector<string> words) {

	Tri * tri = new Tri();
	for (const auto word : words) {
		const auto c_word = word.c_str();
		tri->insert(c_word);
	}

	int answer = 0;
	for (const auto word : words) {
		const auto c_word = word.c_str();
        // 현재의 문자는 하나씩 가지고 있으므로 1로 초기값을 넣어준다.
		answer += tri->find(c_word, 1);
	}

    // 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산한다.
    delete tri;
	return answer;
}

 

---

📄 [구현] 자동완성 With Swift Source Code

import Foundation

func findCharCount(target: String, compare: String, length: Int) -> Int {
    
    var answer = Int.zero
    
    for index in (Int.zero..<length) {
                
        let firstIndex = String.Index(utf16Offset: index, in: target)
        let secondIndex = String.Index(utf16Offset: index, in: compare)
        
        guard target[firstIndex] == compare[secondIndex] else { break }
        
        answer = answer + 1
    }
    
    return answer
}

func solution(_ words: [String]) -> Int {
    
    var answer: [Int] = Array(repeating: Int.min, count: words.count)
    
    // 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력하는지 찾습니다.
    let sortedWords = words.sorted(by: <)
    
    let count = sortedWords.count
    for index in (Int.zero..<count - 1) {
        let previous = sortedWords[index]
        let next = sortedWords[index + 1]
        
        let length = min(previous.count, next.count)
        let matchCount = findCharCount(target: previous, compare: next, length: length)
        
        // 두 문자열의 가장 짧은 길이와 문자열 일치 갯수가 동일한 경우는 해당 문자열이 다음 문자열에 대해서 접두사를 포함하고 있다.
        if length == matchCount {
            answer[index] = max(answer[index], matchCount)
        } else {
            answer[index] = max(answer[index], matchCount + 1)
        }
        
        answer[index + 1] = max(answer[index + 1], matchCount + 1)
    }
    
    // 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력 수 구합니다.
    return answer.reduce(Int.zero, +)
}

---

🚀 REFERENCE

코딩테스트 연습 - [3차] 자동완성 | 프로그래머스

카카오 신입 공채 3차 코딩 테스트 문제 해설

ChangYeop-Yang/Study-Algorithm