티스토리 뷰
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차] 자동완성 (자바)
여기서 이름만 소개했던 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;
}
}
}
'문제풀이 > 백준 && 프로그래머스' 카테고리의 다른 글
[프로그래머스] 문자열 압축 (자바) (2) | 2020.08.27 |
---|---|
[프로그래머스] 무지의 먹방 라이브 (자바) (0) | 2020.08.27 |
[프로그래머스] 블록 이동하기 (자바) (0) | 2020.08.26 |
[프로그래머스] 외벽 점검 (자바) (2) | 2020.08.25 |
[프로그래머스] 자물쇠와 열쇠 (자바) (0) | 2020.08.23 |
- Total
- Today
- Yesterday
- dfs
- 골드
- 레벨3
- 취준
- 신입
- 면접
- 프로젝트
- 후기
- BFS
- 레벨2
- 레벨4
- 코딩테스트
- 브루트포스
- 스프링부트
- 스프링
- 플레
- 게시판
- 그래프이론
- 자료구조
- 카카오
- 백준
- 실버
- 그래프탐색
- 프로그래머스
- 최소스패닝트리
- 구현
- 자바
- 시뮬레이션
- 네이버
- 트리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |