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

작성일: 2024-12-16

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17685

접근 방식

문자열 비교 + 큰 범위이기 때문에, 완전 탐색이 아닌 방식을 이용해야 한다.

잘못된 접근 

import java.util.*;

class Solution {
    public int solution(String[] words) {
        /**
        문자열 연산 + 큰 볌위 => 완전탐색 X
        Map, Stack, Queue와 같은 시간복잡도 O(n)을 이용
        **/

        // 기본 세팅
        int answer = 0;
        Stack<String> stack = new Stack<>();
        String cur = "";

        for(String word:words){
            int idx = 0;

            while(!stack.isEmpty()){
                cur = stack.peek();
                if (idx >= stack.peek().length()) {
                    idx = 0;
                    cur = stack.peek();
                    break;
                    // cur = stack.peek();
                }
                if(word.charAt(idx) == (cur.charAt(idx))){
                    idx++;
                    answer++;
                }else{
                    answer++;
                    idx = 0;
                    stack.pop();
                }
            }
            stack.push(word);
        }
        int idx = 0;
        while(!stack.isEmpty() && idx < cur.length() && cur.charAt(idx) == stack.peek().charAt(idx)){
            idx++;
            answer++;
        }
        return answer;
    }
}

한 시간정도 풀어봤지만, 감을 잡지 못했다.

내 생각엔 한 번에, 모든 단어를 정리해두고 필요한 단어를 찾는 방식으로 해야하지 않나 싶다..

잘 된 접근

어떻게 접근해야 할 지, 도저히 모르겠어서 GPT의 도움을 살짝 받았다.

트라이라는 자료구조를 이용해서 풀 수 있다고 한다.

문제를 풀기 위해, 트리아 자료구조를 공부했다.

트라이란?

출처 : https://ko.wikipedia.org/wiki/트라이_(컴퓨팅)

트리 자료 구조의 일부인데, 이진 트리와는 다르게 키 값을 가지고 있지 않다. 또 하나의 특이점으로는 자식노드를 Map or ArrayList로 구현한다. (해당 부모가 자식으로 문자를 가지고 있는지 확인하기 위해서)

현재 노드와 연관된 키가 무엇인지만을 나타낸다. 값을 저장하지 않기에 문자열 탐색을 빠르게 할 수 있다.

루트는 공백으로 이루어지고, 그 아래에 공백을 부모로 갖는 노드들이 이어진다.

따라서 현재 문제에서는, 공백을 시작으로 하여, 각 문자를 노드를 따라서 모두 연관지은 뒤에
처음 문자열부터 노드를 탐색하며, 리프 노드 or 문자열 완성할 때 까지 탐색한 횟수를 더 해주면 최종 answer값이 될 것이다.

예제 코드

트라이 노드 클래스 구성

class TrieNode{
    Map<Character, TrieNode> child;
    boolean isEnd;
    TrieNode(){
        child = new HashMap<>();
        isEnd = false;
    }
}

트라이 노드 사용 예시

class Solution{
    class TrieNode{
        Map<Character, TrieNode> child;
        boolean isEnd;
        TrieNode(){
            child = new HashMap<>();
            isEnd = false;
        }
    }
    static TrieNode root;
    public int solution(String[] words){
        root = new TrieNode();
        int answer = 0;
        for(String word:words){
            insert(word);
        }

        for(String word:words){
            System.out.println(word + " => 단어 존재 여부 : " + find(word));
        }
        System.out.println("worst => 단어 존재 여부 : " + find("worst"));
        return answer;
    }


    // 단어 삽입
    void insert(String word){
        TrieNode tn = root; // 루트 노드 불러오기
        for(char c:word.toCharArray()){
            tn.child.putIfAbsent(c, new TrieNode()); // 자식이 단어를 가지고 있지 않으면, 새로 노드 생성
            tn = tn.child.get(c); // 노드 위치를 자식으로 변경
        }
        tn.child.isEnd = true; // 마지막 표시
    }

    // 단어 찾기
    boolean find(String word){
        TrieNode tn = root;
        for(char c:word.toCharArray()){
            if(!tn.child.containsKey(c)) return false; // 자식이 가지고 있지 않으면, 등록되지 않은 단어라는 뜻
            tn = tn.child.get(c); // 자식으로 이동
        }

        // 해당 자식을 마지막으로 하는 단어가 존재하는지 여부를 확인
        return tn.isEnd;
    }
}

위 코드를 실행하면, 아래의 결과를 만들어 낸다. 정상적으로 동작함을 알 수 있다.

12-1

기존의 abc, def, ghi, jklm은 등록되었지만, 내가 만들어 낸 worst는 존재하지 않는다.

결과

소스 코드 

import java.util.*;

class Solution{
    class TrieNode{
        Map<Character, TrieNode> child;
        int cnt;
        TrieNode(){
            child = new HashMap<>();
            cnt = 0;
        }
    }
    static TrieNode root;
    public int solution(String[] words){
        root = new TrieNode();
        int answer = 0;

        // 트라이 노드에 단어 넣기
        for(String word:words){
            insert(word);
        }

        // 검색
        for(String word:words){
            answer += search(word);
        }

        return answer;
    }


    // 단어 삽입
    void insert(String word){
        TrieNode tn = root; // 루트 노드 불러오기
        for(char c:word.toCharArray()){
            tn.child.putIfAbsent(c, new TrieNode()); // 자식이 단어를 가지고 있지 않으면, 새로 노드 생성
            tn = tn.child.get(c); // 노드 위치를 자식으로 변경
            tn.cnt++;
        }
    }

    // 단어 검색
    int search(String word){
        TrieNode tn = root;
        int cnt = 0;
        for(char c:word.toCharArray()){
            if(tn.cnt==1) return cnt; // 해당 문자로 시작하는 단어가 없음을 의미
            tn = tn.child.get(c); // 이어지는 문자가 있다면
            cnt++;
        }
        // 끝까지 갔다면, 단어 모두 입력해야 함
        return cnt;
    }
}

바뀐 점이라면, 트라이 노드의 구성을 노드의 끝을 cnt(개수)로 바꿨다는 것이다.

cnt가 1이라는 것은, 해당 노드의 한 번만 방문했다는 뜻이다. 따라서 더 이상, 노드를 탐색할 필요가 없다는 것.

다른 접근 방식

다른 사람들의 풀이를 살펴보니, 대부분 트라이 자료구조를 이용하고 있었는데,

그 중, 정렬을 통해 문자열의 prefix를 비교하는 인상 깊은 코드가 있었다.

import java.util.*;
class Solution {
    public int solution(String[] words) {
        Arrays.sort(words);
        int count = 0;
        for (int i = 0; i < words.length; ++i) {
            int len = compare(words, i);
            if (len == words[i].length()) count += len;
            else count += (len + 1);
        }
        return count;
    }
    private int compare(String[] words, int i) {
        int len = 0;
        if (i > 0) {
            len = prefix(words[i - 1], words[i]);
        }
        if (i < words.length - 1) {
            len = Math.max(len, prefix(words[i], words[i + 1]));
        }
        return len;
    }
    private int prefix(String s1, String s2) {
        int len = 0;
        for (int i = 0; i < Math.min(s1.length(), s2.length()); ++i) {
            if (s1.charAt(i) == s2.charAt(i)) len++;
            else break;
        }
        return len;
    }
}

크게 네 부분으로 나뉘어져 있다.

  1. 주어진 문자열 정렬
  2. 문자열을 for문을 돌면서, i번째 인덱스부터 배열의 모든 문자열을 비교
  3. compare라는 메소드는, 입력받은 문자열 배열과 인덱스를 기준으로 문자열을 비교
  4. prefix 메소드는, 입력받은 두 개의 문자열 중 짧은 문자열 기준으로 for문을 돌리고 몇개의 문자가 다른지 카운트

예를 들어서, {word, world} 라는 문자열 배열이 주어진다면, 처음과 다음을 기준으로 문자열을 비교한다.

i=0부터 시작하면, 두번째 if문에 걸려 0번째와 1번째를 비교한다. wor 세 개가 동일하므로, 3이 return 되어 len은 3이되고 count에 더 해진다. 여기서 +1을 하는 이유는, prefix에 return하는 과정에서 문자열의 값이 다르면 바로 break을 통해 빠져나왔기 때문이다.

그 다음 i=1의 경우에는, 첫 번째 if문에 걸려 다시 0번째와 1번째를 비교하게 된다. 동일하게 3이 리턴되고, count에는 최종적으로 4가 더해져 결과값은 8이 된다.

if문이 두 개로 나뉘어진 이유는, 이전 문자열과 다음 문자열을 비교해서 더 큰 값으로 하기 위함이다.

이 접근 방식의 핵심은 단어를 정렬하는 것에 있다. 정렬을 통해 사전순으로 비교함으로써, 동일한 문자는 주어지지 않는다는 규칙이 존재하기 때문에 앞과 뒤의 단어만을 비교하여 현재 단어를 찾을 수 있는 최소값을 구할 수 있기 때문이다.

알게 된 점

  1. 트라이 자료구조를 알게 되었다. 특히, 문자열의 접두사를 비교하는 과정에서 유용하게 쓰인다.

  2. 단어 검색의 기본인 사전 순을 인지하게 되었다. 우리가 사전에서 단어를 빠르게 찾을 수 있는 것은 단어를 정렬해 두 었기 때문이다. 정렬해 둔 단어를 기반으로, 자음과 모음을 찾기 때문에 굉장히 빠른 속도로 단어를 찾을 수 있다. 이 문제 또한 마찬가지이다. 주어진 문자열 배열을 정렬하고, 앞 뒤 문자만을 비교하여 최솟값을 구할 수 있었다.