프로그래머스 - 가사 검색

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 가사 검색

https://programmers.co.kr/learn/courses/30/lessons/60060

풀이 1. (고급) - Trie 자료구조(시간 복잡도 : (N*L))를 구현하여 해당 가사에 해당하는 words의 수를 체크

import java.util.*;

class Solution {
    static class Node {
		Node [] arr;
		int cnt;
		Node() {
			this.arr = new Node[26];
		}
	}
	static class Trie {
		Node root;
		Trie() {
			this.root = new Node();
		}
		void insert (String s) {
			Node tempNode = root;
			root.cnt++;
			for (int i = 0; i < s.length(); i++) {
				if(tempNode.arr[s.charAt(i)-'a'] == null) {
					tempNode.arr[s.charAt(i)-'a'] = new Node();
					tempNode = tempNode.arr[s.charAt(i)-'a'];
					tempNode.cnt = 1;
				}else {
					tempNode = tempNode.arr[s.charAt(i)-'a'];
					tempNode.cnt++;
				}
			}
		}
		int find (String s) {
			Node tempNode = root;
			for (int i = 0; i < s.length(); i++) {
				if(s.charAt(i) == '?') return tempNode.cnt;
				if(tempNode.arr[s.charAt(i)-'a'] == null) return 0;
				else tempNode = tempNode.arr[s.charAt(i)-'a'];
			}
			return 0;
		}
	}
    public int[] solution(String[] words, String[] queries) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
		int [] answer = new int [queries.length];
		Trie [] front = new Trie[10001];
		Trie [] back = new Trie [10001];
		for(String s : words) {
			if(front[s.length()] == null) {
				front[s.length()] = new Trie();
				back[s.length()] = new Trie();
			}
			front[s.length()].insert(s);
			back[s.length()].insert(new StringBuilder(s).reverse().toString());
		}
		for (int i = 0; i < queries.length; i++) {
			int ans = 0;
			if (map.containsKey(queries[i])) {
				answer[i] = map.get(queries[i]);
				continue;
			}
			if(front[queries[i].length()] != null) {
				if(queries[i].charAt(0) == '?') ans = back[queries[i].length()].find(new StringBuilder(queries[i]).reverse().toString());
				else ans = front[queries[i].length()].find(queries[i]);
			}
			map.put(queries[i], ans);
			answer[i] = ans;
		}

        return answer;
    }
}

풀이 2. (고급) - 풀이 1의 다른 버전

import java.util.*;

class Solution {
    static class Trie {
		Trie [] tries = new Trie[26];
		int count;
		
		public void insert (String s, int idx) {
			if(s.length() == idx) return;
			count++;
			int next = s.charAt(idx) - 'a';
			if(tries[next] == null) tries[next] = new Trie();
			tries[next].insert(s, idx+1);
		}
		
		public int search (String s, int idx) {
			if(s.length() == idx) return 1;
			int result = 0;
			if(s.charAt(idx) == '?') result = count;
			else {
				int next = s.charAt(idx) - 'a';
				if(tries[next] != null) result = tries[next].search(s, idx+1);
			}
			return result;
		}
	}
    public int[] solution(String[] words, String[] queries) {
        Trie [] front = new Trie[10001];
		Trie [] back = new Trie[10001];
		ArrayList <Integer> list = new ArrayList<Integer>();
		
		for (int i = 1; i < 10001; i++) {
			front[i] = new Trie();
			back[i] = new Trie();
		}
		for (String s : words) {
			front[s.length()].insert(s, 0);
			back[s.length()].insert(new StringBuilder(s).reverse().toString(), 0);
		}
		for (String s : queries) {
			if(s.charAt(0) == '?') list.add(back[s.length()].search(new StringBuilder(s).reverse().toString(), 0));
			else list.add(front[s.length()].search(s, 0));
		}
        return list.stream().mapToInt(a -> a).toArray();
    }
}