[프로그래머스] 가사 검색 (자바)

 

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

코딩테스트 연습 - 가사 검색

 

정확성 약 34%, 효율성 약 0.8%의 정답률인 문제입니다.

정확성은 매우 쉽게 풀 수 있습니다.

 

단어 길이별로 ArrayList를 이용해 words와 queries를 하나씩 매칭 해나 가면 됩니다.

하지만 효율성에서 떨어집니다. 무조건 떨어진다고 하네요.

 

정확성 정답, 효율성 오답인 코드

import java.util.*;

public class pm가사검색 {


	public int[] solution(String[] words, String[] queries) {
		ArrayList<String> al[] = new ArrayList[10001];

		for(int i = 1; i <= 10000; i++)
			al[i] = new ArrayList<String>();

		for(String word : words) 
			al[word.length()].add(word);

		int[] answer = new int[queries.length];
		int count, len, index, jndex;
		String temp;

		for(int i = 0; i < queries.length; i++) {
			count = 0;
			String now = queries[i];
			len = now.length();
			index = 0;
			jndex = now.length()-1;
			while(now.charAt(index) == '?')
				index++;
			while(now.charAt(jndex) == '?')
				jndex--;
			now = now.substring(index, jndex+1);

			for(int j = 0; j < al[len].size(); j++) {
				temp = al[len].get(j).substring(index, jndex+1);
				if(now.equals(temp))
					count++;
			}
			answer[i] = count;
		}

		return answer;
	}
}

 

2020/08/21 - [문제풀이/자바] - [프로그래머스] [3차] 자동완성 (자바)

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

여기서 이름만 소개했던 Trie 자료구조나 이분 탐색을 이용하면 풀 수 있다고 합니다.

 

저는 이 문제를 Trie를 이용하여 풀어보겠습니다.

 

 

이 문제의 예제로 주어진 ["frodo", "front", "frost", "frozen", "frame", "kakao"] 중에서 5글자인 단어들로 Trie를 시각화해봤습니다.

각 노드마다 가진 숫자는 하위 단어의 개수입니다. 예를 들어 f-r-o의 숫자는 3인데 fro?? 가 들어온다면 3이 반환됩니다.

트리 형태로 빠르게 탐색이 가능한 자료구조입니다.

 

문제의 특성상 words의 단어의 길이마다 Trie를 만들었습니다.

---

메소드

int solution

'?'는 queries의 앞, 뒤 중 한 곳에 있습니다. 따라서 단어 1개를 앞, 뒤에서 시작하는 Trie로 구성해줍니다.

예를 들어 abcd => trie(a-b-c-d), rtrie(d-c-b-a).

try, catch를 적절히 활용하여 word를 쪼개서 trie의 형태로 구성해줍니다.

 

query의 앞에 '?'가 있다면 reverse 하여 rtrie에서 탐색해줍니다.

word가 dwcba이고 query가 ??cba라면 

rtrie에는 a-b-c-w-d, query의 reverse는 a-b-c-?-? 이므로 탐색이 쉽습니다.

 

class Trie

Trie 자료구조를 생성합니다.

각 노드는 count와 child[26](알파벳)를 가집니다.

생성자는 leaf 노드로 각각 0과 초기화된 Trie[26]을 생성합니다.

 

void insert

char형 배열을 받아 Trie에 연결합니다.

 

int search

'?'가 나오거나 해당 char가 null일 때까지 탐색합니다. 

 

 

public class pm가사검색 {

	public int[] solution(String[] words, String[] queries) {
		Trie trie[] = new Trie[10001];
		Trie rtrie[] = new Trie[10001];

		for(String word : words) { 
			int len = word.length();
			try {
				trie[len].insert(word.toCharArray());
			}
			catch(Exception e) {
				trie[len] = new Trie();
				trie[len].insert(word.toCharArray());
			}
			
			word = new StringBuilder(word).reverse().toString();
			try {
				rtrie[len].insert(word.toCharArray());
			}
			catch(Exception e) {
				rtrie[len] = new Trie();
				rtrie[len].insert(word.toCharArray());
			}
		}
		int[] answer = new int[queries.length];
		int index = 0;
		
		for(String query : queries) {
			if(query.indexOf("?") == 0) {
				query = new StringBuilder(query).reverse().toString();
				try {
				answer[index++] = rtrie[query.length()].search(query.toCharArray());
				}
				catch(Exception e) {
					continue;
				}
			}
			else {
				try {
				answer[index++] = trie[query.length()].search(query.toCharArray());
				}
				catch(Exception e) {
					continue;
				}
			}
		}

		return answer;
	}

	class Trie {
		int count;
		Trie child[];

		Trie() {
			count = 0;
			child = new Trie[26];
		}

		void insert(char cA[]) {
			Trie t = this;
			for(char c : cA) {
				t.count++;
				if(t.child[c-'a'] == null) {
					t.child[c-'a'] = new Trie();
					t = t.child[c-'a'];
				}
				else 
					t = t.child[c-'a'];
			}
		}
		
		int search(char cA[]) {
			Trie t = this;
			for(char c : cA) {
				if(c == '?')
					return t.count;
				
				if(t.child[c-'a'] == null)
					return 0;
				
				t = t.child[c-'a'];
			}
			
			return 0;
		}
	}
}