Programmers
[프로그래머스 Level.4] [3차] 자동완성 (2018 KAKAO BLIND RECRUITMENT) (Java)
Devtraces
2023. 1. 30. 10:41
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/17685
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > [3차] 자동완성
문제 설명
자동완성
포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다!
단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
예를 들어, 학습된 단어들이 아래와 같을 때
go
gone
guild
- go를 찾을 때 go를 모두 입력해야 한다.
- gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
- guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.
이 경우 총 입력해야 할 문자의 수는 7이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
입력 형식
학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.
- 2 <= N <= 100,000
- 2 <= L <= 1,000,000
출력 형식
단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.
입출력 예제
| words | result |
| ["go","gone","guild"] | 7 |
| ["abc","def","ghi","jklm"] | 4 |
| ["word","war","warrior","world"] | 15 |
입출력 설명
- 첫 번째 예제는 본문 설명과 같다.
- 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
- 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
- word는 word모두 입력해야 한다.
- war는 war 까지 모두 입력해야 한다.
- warrior는 warr 까지만 입력하면 된다.
- world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)
나의 코드
트라이(Trie) 자료구조 이용
import java.util.*;
class Solution {
public int solution(String[] words) {
int answer = 0;
Trie trie = new Trie();
for(String word : words)
trie.insert(word);
for(String word : words)
answer += trie.getInputCounts(word);
return answer;
}
class TrieNode {
private Map<Character, TrieNode> childNodes = new HashMap<>(); // 자식 Node들
private int childCount; // 입력된 횟수
}
class Trie {
TrieNode rootNode = new TrieNode();
void insert(String word) {
TrieNode thisNode = this.rootNode;
for(int i=0; i<word.length(); i++) {
thisNode = thisNode.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
thisNode.childCount++;
// computeIfAbsent를 사용하지 않고 구현
// if(!thisNode.childNodes.containsKey(word.charAt(i)))
// thisNode.childNodes.put(word.charAt(i), new TrieNode());
// thisNode = thisNode.childNodes.get(word.charAt(i));
// thisNode.childCount++;
}
}
int getInputCounts(String word) {
int count = 0;
TrieNode thisNode = this.rootNode;
for(int i=0; i<word.length(); i++) {
thisNode = thisNode.childNodes.get(word.charAt(i));
count++;
if(thisNode.childCount == 1)
return count;
}
return count;
}
}
}
풀이
- 텍스트의 자동완성에 많이 쓰이는 자료구조로 Trie 자료구조가 있어 해당 자료구조에 대해 공부하고 문제를 풀었다.
- 루트 노드부터 시작해서 자식 노드로 내려가며 순차적으로 문자를 탐색해 나간다.
자식 노드로 내려가면서 카운팅한다. 이 카운팅하는 수는 결국 문자를 입력한 횟수가 된다.
현재 검색하려는 단어에만 포함되는 문자(카운트가 1)가 나올 때까지 계속 카운팅하면서 자식노드로 내려가며 탐색한다. - 우선 TrieNode 클래스를 만들고 Map과 int형 변수를 만들어준다. 이 Map은 key로 단어의 글자인 Character를 갖고 value로 다시 TrieNode 객체를 갖는다. int형 변수 childCount는 입력된 횟수를 카운팅 할 것이다.
- 그리고 Trie 클래스를 만들어 Trie 객체를 만들면 TrieNode rootNode를 생성하도록 한다. 또한, 이 Trie 클래스 내부에 TrieNode에 단어를 넣기 위한 Map에 자식노드로 뻗어가며 단어의 글자를 집어넣고 각각 입력 횟수를 증가시켜주는 insert 메소드를 구현하고 단어를 다 집어넣고 최소 입력횟수를 카운팅하기 위한 getInputCounts 메소드를 구현한다.
- 우선 Trie trie 인스턴스를 생성하고 주어진 words를 for문을 돌면서 Trie 클래스의 insert 메소드를 이용하여 단어를 모두 집어넣는다.
- insert 메소드를 보면 TrieNode thisNode를 생성하고 여기에 최초 인스턴스에 생성된 TrieNode인 rootNode를 받는다. 이 rootNode부터 시작하여 childNodes에 단어의 글자를 자식노드로 뻗어가며 넣으며 카운팅 하는 것이다.
rootNode의 childNodes에 단어의 첫 글자를 key로 하고 value에 다시 TrieNode를 생성한다. 그리고 이 TrieNode를 다시 thisNode에 받아 이 thisNode의 childCount를 증가시킨다. 그리고 또 다시 다음 글자를 childeNodes에 key로 하고 value에 다시 TrieNode를 생성하고 thisNode에 이 TrieNode를 받고 이 thisNode의 childCount를 증가시키면서 단어의 글자들을 childNodes를 이용해 자식노드로 뻗어가면 된다. 만약 단어의 글자가 있다면 TrieNode를 생성하지 않고 childCount만 증가시키고 해당 TrieNode를 받아 thisNode에 담으면 된다.
(computeIfAbset를 이용하면 Map에 해당 key가 있다면 해당 key의 value를 가져오고 없다면 해당 key의 value로 두 번째 인자인 람다식을 실행한 결과을 넣고 가져온다.) - 따라서 TrieNode rootNode부터 시작해고 단어의 첫 글자부터 탐색하며 childNodes에 해당 글자가 있으면 해당 글자의 value인 TrieNode를 thisNode에 가져오고 해당 childCount를 증가시킨 후에 다음 글자를 thisNode의 childNodes에서 다시 탐색해 나가면 되고 해당 글자가 없다면 thisNode의 childNodes에 해당 글자를 key로 하고 value에 새로운 TrieNode를 갖는 map을 담아주고 해당 단어의 value인 TrieNode를 thisNode에 가져와 이 thisNode의 childCount를 증가시키며 단어의 글자들과 입력 횟수를 담는 것이다.
(루트노드의 자식 노드로 단어의 첫 글자를 넣고 이 첫 글자의 자식 노드로 두 번째 글자를 넣으며 순차적으로 하나하나씩 내려가며 글자를 넣고(있다면 불러오고) 입력 횟수를 카운팅하는 것이다.) - 이렇게 단어들을 다 담았으면 이제 최소 입력횟수를 구하면 된다.
- words를 다시 for문을 돌면서 해당 단어의 최소 입력 횟수를 Trie 클래스의 getInputCounts를 이용하여 구하고 answer에 더해주면 된다.
- TrieNode thisNode를 생성하고 여기에 해당 Trie 인스턴스의 TrieNode rootNode를 받는다. 이제 이 rootNode부터 시작해서 단어의 입력횟수를 카운팅하며 최소 입력횟수까지만 구하면 된다.
- 단어의 길이만큼 for문을 돌며 thisNode의 childNodes에서 단어의 첫 글자를 key로 하는 TrieNode를 찾는다. 그리고 입력횟수를 1 증가시킨다. 이 TrieNode의 childCount가 1이라면 종료하고 아니라면 계속 탐색해 나가면 된다. childCount가 1이라면 1번만 입력되었단 뜻으로 현재 단어에만 입력되었단 뜻으로 해당 글자까지만 누르면 해당 단어를 찾을 수 있다는 것을 나타낸다. 따라서 childCount가 1일 때까지만 탐색한 후 1이 나오면 해당 글자까지의 입력횟수가 최소 입력횟수가 된다.
- 이렇게 단어의 최소입력횟수들을 answer에 계속 더해준 후에 answer를 반환한다.
참고 : https://programmer-chocho.tistory.com/69 , https://woovictory.github.io/2020/04/22/Java-Trie/
문자열 정렬 이용
import java.util.*;
class Solution {
public int solution(String[] words) {
int answer = 0;
Arrays.sort(words);
int[] countArr = new int[words.length];
for(int i=0; i<words.length-1; i++) {
String pre = words[i];
String next = words[i+1];
int minLen = Math.min(pre.length(), next.length());
int sameCharCnt = 0;
for(int j=0; j<minLen; j++) {
if(pre.charAt(j) != next.charAt(j)) break;
sameCharCnt++;
}
if(minLen == sameCharCnt) // next가 pre를 포함하고 있는 경우
countArr[i] = Math.max(countArr[i], sameCharCnt);
else
countArr[i] = Math.max(countArr[i], sameCharCnt+1);
countArr[i+1] = Math.max(countArr[i+1], sameCharCnt+1);
}
for(int i=0; i<countArr.length; i++)
answer += countArr[i];
return answer;
}
}
풀이
- 주어진 배열 words를 오름차순(사전순)으로 정렬한다.
- 각 단어의 최소 입력 횟수를 담을 int형 배열 countArr을 생성한다.
- 이제 사전순으로 정렬된 words를 for문을 돌면서 앞의 문자열과 뒤의 문자열을 비교하여 최소 입력수를 업데이트해 나간다. 바로 뒤의 인덱스에 있는 문자열도 불러올 것이기 때문에 조건식을 i < words.length-1로 한다.
- 앞의 문자열과 뒤의 문자열의 길이를 비교하여 더 짧은 문자열의 길이를 구한다.
- 앞의 문자열과 뒤의 문자열을 첫 글자부터 다른 글자가 나올 때까지 비교하여 같은 글자의 개수를 카운팅한다.
- 이렇게 구한 같은 글자의 개수를 가지고 최소 입력 횟수를 업데이트 해나가면 된다.
- 만약 카운팅 한 개수가 더 짧은 문자열의 길이와 같다면 더 짧은 문자열의 모든 글자를 긴 문자열이 포함하고 있다는 뜻이므로 사전순으로 뒤에 있는 뒤에 문자열이 앞의 문자열을 모두 포함하고 있는 것이다. 따라서 앞의 문자열은 해당 문자열을 모두 입력해야 해당 단어를 구분할 수 있으므로 카운팅한 개수가 입력되어야 하고 뒤의 문자열은 카운팅한 개수보다 한 글자 더 입력하면 해당 단어를 구분 할 수 있으므로 카운팅한 개수 + 1을 입력해야 한다.
- 카운팅 한 개수가 더 짧은 문자열의 길이보다 작다면 앞의 문자열과 뒤의 문자열 모두 같은 글자를 카운팅한 개수보다 한 글자씩 더 입력해야 각각의 단어를 구분 할 수 있으므로 카운팅한 개수 + 1을 입력해야 한다.
- 인덱스 1인 문자열부터는 뒤의 문자열이 되었다가 다음 턴에 앞의 문자열이 되므로 입력 횟수를 업데이트 할 때마다 이미 countArr에 들어가 있는 횟수와 비교하여 더 큰 값을 넣어주도록 한다. (이미 들어가 있는 countArr은 해당 앞 문자열과 최소로 구분 할 수 있는 값이고 이번에 구한 값인 뒤 문자열과 비교했을 때 최소로 구분할 수 있는 값 또한 필수이므로 두 값 중 더 큰 값을 넣어줘야 앞 문자열과 뒤 문자열과 비교했을 때 둘 다 구분이 가능한 최소값이 된다.)
- 이렇게 for문을 돌고나서 모든 단어의 최소 입력값을 구한 다음 countArr을 for문을 돌면서 answer에 모두 더해주고 answer를 반환한다.
참고 : https://wellbell.tistory.com/166