문제 링크: programmers.co.kr/learn/courses/30/lessons/60060
코딩테스트 연습 - 가사 검색
programmers.co.kr
!! 내가 푼 코드는 효율성 테스트를 통과하지 못했다 !!
// 카카오 테크 블로그에서 설명해준 바에 따르면 Trie 자료 구조를 사용하면 되는 듯 하다
// trie를 썼다. 효율성 테스트 12는 이제 통과 하는데 3,4,5가 통과되지 않는다
// 아무래도 arraylist 때문인 것 같다.
import java.util.*;
class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
Trie trie = new Trie();
for(int i = 0; i < words.length; i++) {
trie.add(words[i]);
}
for(int i = 0; i < queries.length; i++) {
if(queries[i].startsWith("?")) {
answer[i] = trie.contains(queries[i], true);
}
else {
answer[i] = trie.contains(queries[i], false);
}
}
return answer;
}
}
class TrieNode{
private HashMap<Character, TrieNode> children = new HashMap<>();
private boolean isLastChar;
private ArrayList<Integer> restLength = new ArrayList<>();
public HashMap<Character,TrieNode> getChildren(){ return this.children; }
public ArrayList<Integer> getRestLength(){ return this.restLength; }
public boolean isLastChar(){ return this.isLastChar; }
public void setIsLastChar(boolean isLastChar){ this.isLastChar = isLastChar; }
}
class Trie{
private TrieNode root;
private TrieNode revRoot;
Trie(){
root = new TrieNode();
revRoot = new TrieNode();
}
public void add(String word){
TrieNode curr = root;
HashMap<Character, TrieNode> children = curr.getChildren();
for(int i = 0; i < word.length() ; i++){
char c = word.charAt(i);
if(!children.containsKey(c)){
curr = new TrieNode();
children.put(c, curr);
}
else{
curr = children.get(c);
}
curr.getRestLength().add(word.substring(i+1).length());
children = curr.getChildren();
}
curr.setIsLastChar(true);
curr = revRoot;
children = curr.getChildren();
for(int i = word.length()-1; i >= 0 ; i--){
char c = word.charAt(i);
if(!children.containsKey(c)){
curr = new TrieNode();
children.put(c, curr);
}
else{
curr = children.get(c);
}
curr.getRestLength().add(word.substring(0,i).length());
children = curr.getChildren();
}
curr.setIsLastChar(true);
}
public int contains(String word, boolean reverse){
TrieNode curr;
if(reverse) {
curr = revRoot;
int count = 0;
for(int i = word.length()-1; i >= 0; i--){
char c = word.charAt(i);
if(c == '?'){
count = 0;
int rest = word.substring(0,i+1).length();
for(int len : curr.getRestLength()){
if(len == rest)
count++;
}
return count;
}
TrieNode node = curr.getChildren().get(c);
if(node == null)
return count;
curr = node;
}
return count;
}
else {
curr = root;
int count = 0;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(c == '?'){
count = 0;
int rest = word.substring(i).length();
for(int len : curr.getRestLength()){
if(len == rest)
count++;
}
return count;
}
TrieNode node = curr.getChildren().get(c);
if(node == null)
return count;
curr = node;
}
return count;
}
}
}
/*
// 정규 표현식을 사용하였다
// 정답은 모두 나왔는데 여전히 효율성 테스트 1~3을 통과하지 못했다.
// 아무래도 O(n^2) 외에 더 좋은 방법이 있는 것 같다.
class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
String qRegx;
for(int i = 0; i < queries.length; i++){
qRegx = getRegx(queries[i]);
for(int j = 0; j < words.length; j++){
if(words[j].matches(qRegx))
answer[i]++;
}
}
return answer;
}
public String getRegx(String q){
String regx="*";
if(q.startsWith("?")){
int len = q.lastIndexOf("?") + 1;
String subQ = q.substring(len);
regx = "^.{"+len+"}"+subQ+"$";
}
else if(q.endsWith("?")){
int len = q.length() - q.indexOf("?");
String subQ = q.substring(0, q.indexOf("?"));
regx = "^"+subQ+".{"+len+"}$";
}
return regx;
}
}
*/
/*
// 정답은 나오나 효율성 테스트를 통과하지 못함
class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
for(int i = 0; i < queries.length; i++){
int[] position = getWCPosition(queries[i]);
answer[i] = isMatch(words, queries[i], position);
}
return answer;
}
public int[] getWCPosition(String q){
int[] position = {-1,-1}; // head일 경우 1, tail일 경우 2
char[] strCharArray = q.toCharArray();
for(int i = 0; i < strCharArray.length; i++){
if(strCharArray[i] == '?'){
if(position[0] == -1){
if(i == 0)
position[0] = 1;
else{
position[0] = 2;
position[1] = i;
}
}
else if(position[0] == 1){
if(i == strCharArray.length - 1 || strCharArray[i+1] != '?')
position[1] = i+1;
}
}
}
return position;
}
public int isMatch(String[] words, String query, int[] p){
int count = 0;
String subQuery;
int wcLength = 0;
if(p[0] == 1) {
subQuery = query.substring(p[1]);
wcLength = query.substring(0,p[1]).length();
}
else {
subQuery = query.substring(0, p[1]);
wcLength = query.substring(p[1]).length();
}
for(int i = 0; i < words.length; i++){
String subWord;
int wordWCLength;
try{
if(p[0] == 1) {
subWord = words[i].substring(p[1]);
wordWCLength = words[i].substring(0,p[1]).length();
}
else {
subWord = words[i].substring(0, p[1]);
wordWCLength = words[i].substring(p[1]).length();
}
if(wcLength != wordWCLength)
continue;
if(subWord.equals(subQuery))
count++;
}
catch(Exception e){}
}
return count;
}
}
*/효율성 테스트도 통과한 코드들은 아래의 블로그에서 확인할 수 있다.
[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 가사 검색 (Java)
프로그래머스 2020 KAKAO BLIND RECRUITMENT 가사 검색 : https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 | 프로그래머스 programmers.co.kr 예전에 못 풀었다가 다시 한..
leveloper.tistory.com
[2020카카오공채] 가사 검색
문제출처: https://programmers.co.kr/learn/courses/30/lessons/60060 문제 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키
velog.io
이 문제를 풀면서 Trie에 대해 알게 되었다.
Trie는 특히 문자 검색을 할 때 많이 쓰이는데 자동 완성도 trie를 이용한 것이라고 한다.
String의 한 character씩을 모두 노드로 만들고, 나중에 나오는 character가 먼저 나오는 character의 자식 노드가 되는 트리의 한 종류이다. 이렇게 하면 front, frodo 와 같이 공통으로 시작하는 문자의 경우 탐색 시간이 훨씬 줄어든다.
다음은 Trie를 공부하면서 짠 자바 코드이다.
class TrieNode{
char val;
private HashMap<Character, TrieNode> child = new HashMap<>();
private boolean isLastChar;
TrieNode(){}
TrieNode(char val){
this.val = val;
}
HashMap<Character, TrieNode> getChild(){
return this.child;
}
boolean isLastChar() {
return this.isLastChar;
}
void setIsLastChar(boolean isLastChar) {
this.isLastChar = isLastChar;
}
}
class Trie{
private TrieNode root;
public Trie(){
root = new TrieNode();
}
void insert(String word) {
TrieNode curr = this.root;
HashMap<Character, TrieNode> child = curr.getChild();
for(char ch: word.toCharArray()) {
if(!child.containsKey(ch)) {
curr = new TrieNode(ch);
child.put(ch, curr);
}
else {
curr = child.get(ch);
}
child = curr.getChild();
}
curr.setIsLastChar(true);
}
boolean contains(String word) {
TrieNode curr = root;
for(char ch: word.toCharArray()) {
TrieNode child = curr.getChild().get(ch);
if(child == null)
return false;
curr = child;
}
return curr.isLastChar();
}
void delete(String word) {
delete(root, word, 0);
}
private boolean delete(TrieNode curr, String word, int index) {
if(index == word.length()) {
if(!curr.isLastChar())
return false;
curr.setIsLastChar(false);
return curr.getChild().isEmpty();
}
char ch = word.charAt(index);
TrieNode node = curr.getChild().get(ch);
if(node == null)
return false;
boolean deleteCurrNode = delete(node, word, index+1) && !node.isLastChar();
if(deleteCurrNode) {
curr.getChild().remove(ch);
return curr.getChild().isEmpty();
}
return false;
}
}어떤 사람들은 람다를 사용했는데 확실히 람다를 사용하면 코드가 훨씬 간단해진다.
람다를 사용하고자 한다면 insert 부분을 다음과 같이 바꾸면 된다.
void insert(String word) {
TrieNode curr = this.root;
HashMap<Character, TrieNode> child = curr.getChild();
for(char ch: word.toCharArray()) {
curr = curr.getChild().computeIfAbsent(ch, c -> new TrieNode());
}
curr.setIsLastChar(true);
}
'Study Log > Algorithm' 카테고리의 다른 글
| Programmers / 정렬 - K번째 수 (0) | 2021.04.17 |
|---|---|
| Programmers / Hash - 완주하지 못한 선수 (0) | 2021.04.06 |
| 카카오 2020 블라인드 채용 1차 코딩테스트 3번 문제 - 자물쇠와 열쇠 (0) | 2020.09.07 |
| 카카오 2020 블라인드 채용 1차 코딩테스트 2번 문제 - 괄호 변환 (0) | 2020.09.05 |
| 카카오 2020 블라인드 채용 1차 코딩테스트 1번 문제 - 문자열 압축 (0) | 2020.09.04 |
댓글