[2020 카카오 블라인드 코딩테스트] 가사 검색 JAVA

 

[문제]

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

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

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다.
예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

 

[가사 단어 제한사항]
- words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
- 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

[검색 키워드 제한사항]
- queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
- 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.검색 키워드는 중복될 수도 있습니다.
- 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
- 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
-> 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

[입출력 예]

- "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
- "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
- "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
- "fro???"는 "frozen"에 매치되므로 1입니다.
- "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

 

---

 

[Solution 1]
- 이진탐색 사용 X
 - 정확성 테스트 18/18 통과 (25.0)
 - 효율성 테스트 2/5 통과 (30.0)
 - 합계 55.0 / 100.0

package programmers_가사검색;

public class Main {
	public static void main(String[] args) {
		//TEST CASE
		String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
		String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?"};
		
		int[] sol = Solution(words, queries);
		
		for(int i=0; i<sol.length; i++) {
			System.out.print(sol[i]+" ");
		}
	}

	static int[] Solution(String[] words, String[] queries) {
		int[] answer = new int [queries.length];
		
		for(int i=0; i<queries.length; i++) {
			char tmp = queries[i].charAt(0);		//쿼리의 첫번째 단어
			
			String compareStr = "";
			boolean location = false;		//와일드카드의 위치 -> true:접두사에	false:접미사에 위치
			int qcnt = 0;					//와일드카드 COUNT
			
			//와일드카드가 접두사에 위치
			if(tmp == '?') {
				location = true;
				qcnt = 1;
			} else {
				//와일드카드가 접미사에 위치하면 첫번째 알파벳 연결
				compareStr = Character.toString(tmp);
			}
			
			//두번째 알파벳부터 탐색
			for(int j=1; j<queries[i].length(); j++) {
				tmp = queries[i].charAt(j);
				
				if(tmp == '?') {
					qcnt++;				//와일드카드면 와일드카드 CNT++
				} else {
					compareStr += Character.toString(tmp);		//알파벳이라면 뒤에 단어들과 비교할 compareStr에 연결해줌
				}
			}
			
			//단어들과 비교 시작
			int ansCnt = 0;
			for(int j=0; j<words.length; j++) {
				if(words[j].length() != compareStr.length()+qcnt) continue;				//단어와 길이가 다르면 비교할 필요X
				
				if(location) {
					//와일드카드가 접두사에 위치하면 와일드카드CNT(qcnt) 이후부터 알파벳과 비교
					if(words[j].substring(qcnt, words[j].length()).equals(compareStr)) ansCnt++;
				} else {
					//와일드카드가 접미사에 위치하면 첫번째부터 qcnt까지의 알파벳과 비교
					if(words[j].substring(0, compareStr.length()).equals(compareStr)) ansCnt++;
				}
			}
			answer[i] = ansCnt;
		}
		
        return answer;
    }
}

 

 

[Solution 2]
- 이진탐색 사용
- Lower Bound, Upper Bound 구현

package programmers_가사검색;

import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String[] args) {
		String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
		String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?"};
		
		int[] sol = Solution(words, queries);
		
		for(int i=0; i<sol.length; i++) {
			System.out.print(sol[i]+" ");
		}
	}

	static int[] Solution(String[] words, String[] queries) {
		ArrayList<ArrayList<String>> arr = new ArrayList<ArrayList<String>>();
		ArrayList<ArrayList<String>> revArr = new ArrayList<ArrayList<String>>();
		
		int[] answer = new int [queries.length];
		
		//단어의 길이별로 Array Init
		for(int i = 0; i < 10001; i++) { 
			arr.add(new ArrayList<String>()); 
			revArr.add(new ArrayList<String>());
		}
		
		//단어들 역방향으로 저장
		for(int i=0; i<words.length; i++) {
			String word = words[i];
			arr.get(word.length()).add(word);
			revArr.get(word.length()).add((new StringBuffer(word)).reverse().toString());
		}
		
		//단어 정렬
		for(int i=0; i<10001; i++) {
			Collections.sort(arr.get(i));
			Collections.sort(revArr.get(i));
		}

		//쿼리문의 와일드카드 위치 확인
		for(int i=0; i<queries.length; i++) {
			int ansCnt = 0;
			//와일드카드가 접두에 위치 -> 쿼리도 뒤집어서 revArr와 비교
			if(queries[i].charAt(0) == '?') {
				String tmp = (new StringBuffer(queries[i])).reverse().toString();		//쿼리 단어 뒤집
				
				//쿼리의 ?들이 표현할 수 있는 가장 작은값과 가장 큰값으로 만들어서(replace) 찾기
				int rightIndex = upper_bound(revArr.get(queries[i].length()), tmp.replaceAll("\\?", "z"));	//인자값(ex: frozzz)보다 큰 첫번째 idx
				int leftIndex = lower_bound(revArr.get(queries[i].length()), tmp.replaceAll("\\?", "a"));	//인자값(ex: froaaa)과 같거나 큰 첫번째 idx
				
				ansCnt = rightIndex - leftIndex;		//초과 위치 - 시작 위치
			} else {		//와일드카드가 접미에 위치 -> arr와 비교
				int rightIndex = upper_bound(arr.get(queries[i].length()), queries[i].replaceAll("\\?", "z"));
				int leftIndex = lower_bound(arr.get(queries[i].length()), queries[i].replaceAll("\\?", "a"));
				
				ansCnt = rightIndex - leftIndex;
			}
			answer[i] = ansCnt;
		}
		
        return answer;
    }
	
	//lower_bound : 주어진 인자값(target)보다 크거나 같은 값이 처음 나올 때의 위치 return
	static int lower_bound(ArrayList<String> list, String target) {
		int begin = 0;
		int end = list.size();
		
		while(begin < end) {
			int mid = (begin+end)/2;
			//list[mid]가 target보다 사전순으로 같거나 크면(뒤에 있으면)
			if(list.get(mid).compareTo(target) >= 0) end = mid;
			else begin = mid + 1;
		}
		
		return begin;
	}

	//upper_bound : 인자값(target)보다 큰 첫번째 위치를 반환
	static int upper_bound(ArrayList<String> list, String target) {
		int begin = 0;
	    int end = list.size();
	    
	    while(begin < end) {
	    	int mid = (begin+end)/2;
	    	
	    	//list[mid]가 target보다 작거나 같으면
	    	if(target.compareTo(list.get(mid)) >= 0) begin = mid + 1;
	    	else end = mid;
	    }
	    
	    return begin;
	}
}