본문 바로가기
알고리즘

알고리즘 / Java / 2020 카카오 블라인드 / 가사 검색

ordinCode 2020. 8. 8. 12:53

카카오 블라인드 테스트 - 가사 검색

 

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

 

programmers.co.kr

 

문제의 자세한 정보는 위 링크를 참고해주세요.

 

알고리즘 / 2020 카카오 블라인드 테스트 / 가사 검색

문제 정리

문제의 요지는 간단합니다.

words 배열이 있고, queries가 주어지면 각 query에 부합하는 word가 몇개있는지 찾는거죠.

언뜻보면 쉬워보이지만, 효율성 테스트를 통과하려면 몇 가지 장치를 마련해야합니다.

 

문제 해결에 필요한 것

1. 캐싱

검색 키워드 제한사항

  • queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
  • 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
  • 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
  •  검색 키워드는 중복될 수도 있습니다. 
  • 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항을 보면  키워드는 중복 될 수 있다고 합니다. 따라서 효율성 테스트를 통과하기 위해서는 한번 나왔던 queries는 값을 기억하고 있는게 좋겠죠.

다음과 같이 해쉬맵으로 캐시 기능을 사용해줍니다.

class Solution {
    private Map<String, Integer> cache = new HashMap<>();
    
    ...
    
}

 

2. 트리

이번 문제를 효율적으로 풀기위해서는 트리가 필요합니다. 그럼 트리가 왜 필요한 지 한번 생각보도록하죠.

트리가 없다면?

트리가 없는 경우를 대충 생각해보면 queries에 있는 요소들을 하나씩 꺼내서 words에 있는 요소들과 비교하느라 이중for문을 돌아야 합니다.

즉, 시작 복잡도가 O(n²)입니다.

트리를 쓴다면?

트리를 쓰는 경우도 한번 간단하게 생각해보겠습니다. 주어진 words를 가지고 트리를 만들어 놓으면 쿼리를 하나씩 꺼내서 비교할 때 words를 다 돌지 않아도 된다는 이점이 있습니다. 우리가 만들 트리의 모습은 대강 이렇습니다.

 

 

 

루트 아래에 있는 숫자는 words 단어 길이로 구분한 것이고, 빨간색 숫자는 해당 노드로부터 파생되는 리프 노드의 갯수, 즉 일치하는 단어들의 갯수입니다.

 

그렇다면 트리를 만드는 경우의 시간복잡도를 생각해볼까요?

일단 트리를 만드는 비용이 있겠네요. 일단 words들을 전체적으로 한번 돌면서 트리를 만들기 때문에 n차원의 시간이 소요됩니다.

문제의 특성상 words를 가지고 트리를 한 번 만들고, word 들을 뒤집어서 거꾸로 된 트리도 하나 필요하기 때문에 트리를 2번 만들어야 하지만 결국 O(n)의 복잡도 입니다. (O(n) 이나 O(2n), O(10n)도 O(n))

그리고 query를 하나씩 가져와 트리를 탐색하는 과정에서도 n차원의 시간이 소요되겠네요.

무언가 이런저런 작업을 많이 하는 것처럼 보이지만 이중 for문을 사용한다든가 하는 일은 없기 때문에 결과적으로 O(n)보다는 크고 O(n²)보다는 적은 시간이 걸린다는 것을 알 수 있습니다.

 

트리 구현하기

그럼 이제 Solution.java 클래스 안에 내부 클래스로 트리를 한번 구현해보도록 하겠습니다.

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<String, Integer> cache = new HashMap<>();
    
    class Trie {
    	private TrieNode rootNode;

        public Trie() {
            this.rootNode = new TrieNode();
            
        public TrieNode getRootNode() {
            return rootNode;
        }    
    }
    
    class TrieNode {
        private final HashMap<Character, TrieNode> childNode = new HashMap<>();
        private int value = 1;

        public HashMap<Character, TrieNode> getChildNode() {
            return childNode;
        }
        
        public void setValue(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    }
}

기본적인 뼈대는 위와 같습니다.

이제 word를 전달하면 트리로 만들어주는 insert메서드가 필요합니다.

insert()

void insert(String word) {
	TrieNode thisNode = this.rootNode;
	for (int i = 0; i < word.length(); i++) {
		thisNode = thisNode.getChildNode().computeIfAbsent(word.charAt(i), x -> new TrieNode());
	}
}

그리고 위 트리그림의 빨간 글씨부분인 TrieNode의 value 부분을 셋팅할 메서드도 필요합니다.

public void setLetfNodeCount(TrieNode node) {
	HashMap<Character, TrieNode> childMap = node.getChildNode();
	//만약 자식 노드가 없으면 리턴(기본값 1을 사용)
	if (childMap.size() == 0) {
		return;
	}
	//자식 노드가 있으면 자식노드 먼저 방문, 후위 순회를 떠올리면 쉽습니다.
	for (TrieNode childNode : childMap.values()) {
		setSubTreeCount(childNode);
	}
	//자식 노드 방문후에는 자식노드들의 value를 합한 값으로 해당 노드의 value값을 설정
	int count = 0;
	for (TrieNode childNode : childMap.values()) {
		count += childNode.getValue();
	}
	node.setValue(count);
}

이로써 트리를 만드는데 필요한 것들은 준비가 되었습니다.

마지막으로 종합해서 트리를 만드는 메서드를 만들죠

makeTrie()

public Trie makeTrie(String[] words, Boolean isReversed) {
	Trie trie = new Trie();
	for (String word : words) {
		String wordWithLength = makeWordToInputTree(word, isReversed);
		trie.insert(wordWithLength);
	}
	trie.setLeftNodeCount(trie.getRootNode());
	return trie;
}

private String makeWordToInputTree(String word, Boolean isReversed) {
	StringBuilder builder = new StringBuilder(word);
	if (isReversed) {
		builder.reverse();
	}
	return builder.insert(0, word.length()).toString();
}

 

지금까지의 전체 코드는 다음과 같습니다.

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<String, Integer> cache = new HashMap<>();

    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];

        Trie trie = makeTrie(words, false);
        Trie reversTrie = makeTrie(words, true);
        
        return answer;
    }

    class Trie {
        private TrieNode rootNode;

        public Trie() {
            this.rootNode = new TrieNode();
        }

        void insert(String word) {
            TrieNode thisNode = this.rootNode;
            for (int i = 0; i < word.length(); i++) {
                thisNode = thisNode.getChildNode().computeIfAbsent(word.charAt(i), x -> new TrieNode());
            }
        }

        public void setLeftNodeCount(TrieNode node) {
            HashMap<Character, TrieNode> childMap = node.getChildNode();
            if (childMap.size() == 0) {
                return;
            }
            for (TrieNode childNode : childMap.values()) {
                setLeftNodeCount(childNode);
            }
            int count = 0;
            for (TrieNode childNode : childMap.values()) {
                count += childNode.getValue();
            }
            node.setValue(count);
        }
        
		public TrieNode getRootNode() {
			return rootNode;
        }
    }

    class TrieNode {
        private final HashMap<Character, TrieNode> childNode = new HashMap<>();
        private int value = 1;

        public HashMap<Character, TrieNode> getChildNode() {
            return childNode;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    }

    public Trie makeTrie(String[] words, Boolean isReversed) {
        Trie trie = new Trie();
        for (String word : words) {
            String wordWithLength = makeWordWithLength(word, isReversed);
            trie.insert(wordWithLength);
        }
        trie.setLeftNodeCount(trie.getRootNode());
        return trie;
    }

    private String makeWordWithLength(String word, Boolean isReversed) {
        StringBuilder builder = new StringBuilder(word);
        if (isReversed) {
            builder.reverse();
        }
        return builder.insert(0, word.length()).toString();
    }
}

 

문제 풀이

위에서 힘든 과정은 이미 거의 다 끝났습니다. 이제 query를 하나씩 꺼내서 다음 과정을 진행합니다.

  • 캐시에 있는지 확인한다. -> 캐시에 있다면 캐싱된 값을 가져오고 다음 query로 넘어간다.
    • 캐시에 없다면 ?가 query의 앞에 있는지 뒤에 있는지 확인해서 ?가 앞에 있다면 거꾸로된 query를 거꾸로된 트리에서 탐색한다.
    • 결과 값을 캐시에 저장한다.

위의 과정을 코드로 표현하면 다음과 같습니다.

for (int i = 0; i < queries.length; i++) {
	//캐시에 있는지 확인
	if (cache.containsKey(queries[i])) {
		answer[i] = cache.get(queries[i]);
		continue;
	}

	int matchCount = 0;
	if (queries[i].charAt(0) == '?') {
		matchCount = reversTrie.getCount(makeWordWithLength(queries[i], true));
	} else {
		matchCount = trie.getCount(makeWordWithLength(queries[i], false));
	}
	cache.put(queries[i], matchCount);
	answer[i] = matchCount;
}

...
class Trie {
	...
	//getCount()
    //query를 기준으로 tree를 탐색해 나가다가 "?"가 나오면 현재 노드의 값을 가져옵니다.
	public int getCount(String query) {
		TrieNode thisNode = this.rootNode;
		for (int i = 0; i < query.length(); i++) {
			char character = query.charAt(i);
			if (character == '?') {
				break;
			}
			thisNode = thisNode.getChildNode().get(character);
			if (thisNode == null) {
				return 0;
			}
		}
	return thisNode.getValue();
	}

}

 

마지막으로 "?"로만 구성된 query인 마스터쿼리인 경우만 고려해주면 끝이 납니다.

마스터쿼리일때는 위의 getCount메서드에 query의 길이 + "?"인 인자를 던져주면 되겠죠? 예시 : "?????" -> getCount("5?")

 

마지막으로 모든 코드는 다음과 같습니다.

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<String, Integer> cache = new HashMap<>();

    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];

        Trie trie = makeTrie(words, false);
        Trie reversTrie = makeTrie(words, true);

        for (int i = 0; i < queries.length; i++) {
            if (cache.containsKey(queries[i])) {
                answer[i] = cache.get(queries[i]);
                continue;
            }

            int matchCount = 0;
            if (isMaterQuery(queries[i])) {
                matchCount = trie.getCount(queries[i].length() + "?");
            } else {
                if (queries[i].charAt(0) == '?') {
                    matchCount = reversTrie.getCount(makeWordWithLength(queries[i], true));
                } else {
                    matchCount = trie.getCount(makeWordWithLength(queries[i], false));
                }
            }
            answer[i] = matchCount;
            cache.put(queries[i], matchCount);
        }

        return answer;
    }

    public Trie makeTrie(String[] words, Boolean isReversed) {
        Trie trie = new Trie();
        for (String word : words) {
            String wordWithLength = makeWordWithLength(word, isReversed);
            trie.insert(wordWithLength);
        }
        trie.setLeftNodeCount(trie.getRootNode());
        return trie;
    }

    private String makeWordWithLength(String word, Boolean isReversed) {
        StringBuilder builder = new StringBuilder(word);
        if (isReversed) {
            builder.reverse();
        }
        return builder.insert(0, word.length()).toString();
    }

    private boolean isMaterQuery(String query) {
        return query.charAt(0) == '?' & query.charAt(query.length() - 1) == '?';
    }

    class Trie {
        private TrieNode rootNode;

        public Trie() {
            this.rootNode = new TrieNode();
        }

        void insert(String word) {
            TrieNode thisNode = this.rootNode;
            for (int i = 0; i < word.length(); i++) {
                thisNode = thisNode.getChildNode().computeIfAbsent(word.charAt(i), x -> new TrieNode());
            }
        }

        public void setLeftNodeCount(TrieNode node) {
            HashMap<Character, TrieNode> childMap = node.getChildNode();
            if (childMap.size() == 0) {
                return;
            }
            for (TrieNode childNode : childMap.values()) {
                setLeftNodeCount(childNode);
            }
            int count = 0;
            for (TrieNode childNode : childMap.values()) {
                count += childNode.getValue();
            }
            node.setValue(count);
        }

        public int getCount(String query) {
            TrieNode thisNode = this.rootNode;
            for (int i = 0; i < query.length(); i++) {
                char character = query.charAt(i);
                if (character == '?') {
                    break;
                }
                thisNode = thisNode.getChildNode().get(character);
                if (thisNode == null) {
                    return 0;
                }
            }
            return thisNode.getValue();
        }

        public TrieNode getRootNode() {
            return rootNode;
        }
    }

    class TrieNode {
        private final HashMap<Character, TrieNode> childNode = new HashMap<>();
        private int value = 1;

        public HashMap<Character, TrieNode> getChildNode() {
            return childNode;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }
    }
}
반응형

'알고리즘' 카테고리의 다른 글

알고리즘 / Java / 프로그래머스 - 여행경로  (0) 2020.09.02
알고리즘 / Java / 프로그래머스 - 단어 변환  (0) 2020.09.01
알고리즘 / [java] 2020 카카오 블라인드 테스트 / 괄호 변환  (0) 2020.07.26
알고리즘 / [java] 주식가격 / 프로그래머스  (0) 2020.07.25
알고리즘 / [java] 기능개발 / 프로그래머스  (1) 2020.06.05

'알고리즘' Related Articles

티스토리툴바