[프로그래머스] 2020 카카오 #4 가사 검색 (Java)

#4 가사 검색

난이도 : LEVEL 4

유형 : 자료구조, Map, 정렬, 이진탐색

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

▸ 문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

 

문제 풀이  

카카오 기출은 풀때마다 미지의 모험을 하는 느낌이다. 노트없으면 절대 풀 수 없는 복잡한 설계와 난이도를 갖고있다. 과연 실전에서 풀 수 있었을까 궁금하다. 그래도 비슷한 문제 풀이 경험이 있어서(21년도 기출) 다행히 잘 접근할 수 있었다. 해당 문제는 새로운 규칙을 만드는 문제는 아니고 효율성을 끌어올리기 위해 자료구조에 대해 심도있게 다뤄보라고 제시하는 것 같다.

 

구상

일단 큰 그림으로 잡아보면 결국 queries와 words를 각각 비교하면 일치하는 문자의 갯수를 구하면된다. 그래서 일단 구해봤다.

 

처음에 필요한 데이터는 쿼리의 길이(len), 와일드카드를 제외한 쿼리의 길이(cutLen), 접두사/접미사 여부(flag)라고 설계했다.

• 쿼리의 길이(len)은 당연히 맨 처음 대조해보기 가장 쉬운 데이터이다.
• 와일드카드를 제외한 쿼리의 길이(cutLen)은 words들과 비교할 때 words 문자열을 잘라줄 때 필요하다.
• 접두사/접미사 여부(flag)는 말그대로 쿼리가 앞에서 시작하는 것인지 뒤에서 시작하는 것인지 알기위해 필요하다.

 

수도 코드는 다음과 같다.

1. 각 쿼리에 해당하는 words의 갯수를 구하는 것이므로 하나의 쿼리에 words를 돌려줘야한다. (1쿼리 → 모든 words)
2. 쿼리의 와일드 카드('?')는 무조건 하나 이상 포함되어 있으며, 접두사 혹은 접미사로 붙어있고 연속되어 있다. 그러므로 맨 앞에 글자만 확인하여 와일드 카드가 접두사에 있는지 접미사에 있는지 구분해준다. if(query.charAt(0)=='?')
3. 쿼리의 와일드 카드를 모두 제거해주고, 남은 쿼리의 길이(cutLen)를 구한다. query = query.replace("?", "");
4. words들을 남은 쿼리의 길이에 맞게 잘라주고 일치하는지 비교해준다.
   1. if(접미사), w = w.substring(w.length()-cutLen, w.length());
   2. else(접두사), w = w.substring(0,cutLen);
                   

 

풀이 코드  (정확성 100%, 효율성 2/5)

이렇게 구하니 정확성은 100%이고 효율성은 3개만 틀렸다.

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

		for(int i=0; i<qLen ;i++) {
			String query = queries[i];
			int totalLen = query.length();
			boolean flag = false;

			// ? 위치 접두사 true / 접미사 false
			if(query.charAt(0)=='?') {
				flag = true;
			}
			query = query.replace("?", "");
			int cutLen = query.length();
			int cnt=0;
			for(int j=0; j<wLen; j++) {
				String w = words[j];
				if(w.length()!=totalLen) continue;
				if(flag) {
					w = w.substring(w.length()-cutLen, w.length());
				}else {
					w = w.substring(0,cutLen);
				}
				if(query.equals(w)) {
					++cnt;
				}
			}
			answer[i]= cnt;
		}
		return answer;
	}
}

 

 

문제 풀이 2

만약 효율성에서 하나도 통과못했으면 아예 설계 방향을 틀어버렸을 수도 있는데 다행히 3개만 남은 것을 보고 조금만 더 개선해주면 통과할 것 같았다. 

 

구상

비교할 수 있는 데이터가 무엇일까 고민하다가 문자의 길이(len)를 지표로 사용하고 query와 문자열 자체들을 비교해주기로 정했다. 전체적으로 돌아가는 로직의 구상은 다음과 같다.

• '쿼리의 길이가 5일 때 words 길이가 5인 List를 불러온다. List에 들어있는 문자열들 중 쿼리에 해당하는 구간을 구해준다. 그리고 그 구간의 길이를 구해주면 된다.'

List에 들어있는 문자열들 중 쿼리에 해당하는 구간

위의 로직에서 말한 구간을 구하려면 문자열들을 비교할 수 있어야 한다.  만약 'pr???'라는 쿼리가 있다면 해당 쿼리에 해당하는 문자열의 전체 구간은 'praaa' ~ 'przzz'이다. 이를 코드로 구현해주면 된다.

 

그럼 만약 와일드 카드가 접두사부터 시작하는 '????o'라는 쿼리는 어떻게 구할까?  'aaaao'~'zzzzo'를 구하면 안된다. 그러면 'bbbbb'와 같은 단어도 포함되기 때문에 뒤에 'o'만 오는 문자만 따로 구할 수가 없다. 그래서 그냥 문자를 뒤집어주면 된다. 쿼리와 문자 둘 다 뒤집어서 'o????'에 해당하는 'oaaaa'~'ozzzz'를 구해주면 된다.

 

설계

1. Map<Integer, List<String>>자료구조를 사용하여 Key에는 문자열의 길이를 담고 Value에는 그에 해당하는 word를 넣어준다.
   1. List<String>을 따로 꺼내어 안에 들어있는 word를 오름차순으로 정렬해준다.
   2. 거꾸로된 문자들의 데이터(rData)도 따로 저장해준다
2. query를 모두 반복문을 돌려 그에 해당하는 문자들의 갯수를 구한다.
   1. 와일드카드가 접두사부터 시작하면 거꾸로된 문자 데이터 rData를 사용한다. 쿼리도 뒤집어줘야 한다.
   2. 와일드카드가 접미사부터 시작하면 원본 그대로 Data를 사용한다.
   3. 쿼리 길이에 해당하는 문자가 없으면 0
   4. 중요! 쿼리 최소 문자열 '?' → 'a', 쿼리 최대 문자열 '?' → 'z'에 해당하는 구간을 이진탐색을 통해 구해준다.
      1. String minQuery = query.replace('?', 'a'); // s
      2. String maxQuery = query.replace('?', 'z'); // e
   5. 이렇게 구한 쿼리에 해당하는 구간의 길이를 저장해준다. answer[i] = e-s;

 

풀이 코드  (최종)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
	static Map<Integer, ArrayList<String>> data,rData;
	static ArrayList<String> in,rIn;
	public int[] solution(String[] words, String[] queries) {
		int wLen = words.length; 
		int qLen = queries.length;
		int[] answer = new int[qLen];

		// len, words 
		data = new HashMap<>();
		rData= new HashMap<>();
		for(int i=0; i<wLen ;i++) {
			String word = words[i];
			String reverseWord = reverseString(word);
			int totalLen = word.length();

			if(!data.containsKey(totalLen)) {
				in = new ArrayList<>();
				in.add(word);
				rIn = new ArrayList<>();
				rIn.add(reverseWord);
				data.put(totalLen, in);
				rData.put(totalLen, rIn);
			}else {
				data.get(totalLen).add(word);
				rData.get(totalLen).add(reverseWord);
			}
		}

		// map에 저장된 word 오름차순 정렬 
		for(int len : data.keySet()) {
			List<String> list = data.get(len);
			List<String> rList = rData.get(len);
			Collections.sort(list);
			Collections.sort(rList);
		}

		for(int i=0; i<qLen; i++) {
			String query = queries[i];
			int totalLen = query.length();

			// ? 위치 접두사 false / 접미사 true
			List<String> wordList;
			if(query.charAt(0)=='?') {
				wordList = rData.get(totalLen);
				query = reverseString(query);
			}else {
				wordList = data.get(totalLen);
			}

			if(!data.containsKey(totalLen)) {
				answer[i] = 0;
				continue;
			}

			// 이진탐색 
			int s=0,e=0;
			String minQuery = query.replace('?', 'a');
			String maxQuery = query.replace('?', 'z');
			s = search(wordList, minQuery);
			e = search(wordList, maxQuery);
			answer[i] = e-s;
		}
		return answer;
	}

	static int search(List<String> wordList, String query) {
		int start =0, end =wordList.size();
		while(start<end) {
			int mid = (start+end)/2;
			// query >= word
			if(query.compareTo(wordList.get(mid))>=0) {
				start =mid+1;
			}else {
				end = mid;
			}
		}
		return start;
	}

	static String reverseString(String s) {
		return new StringBuffer(s).reverse().toString();
	}
}

 

 

왼(브루트포스), 오른(이진탐색)

 

그냥 비교해봤다. 주황색 선 밑으로 시간이 비선형 관계를 이루며 증가하는 것을 볼 수 있다. 코드 몇 줄로 이렇게 할 수 있다니 재밌다. 그런데 풀고 다른 풀이들을  보니 다 Trie 자료구조로 풀이를 했다. Trie 저번에 한 번 훑고 넘긴 기억이 있는데 이제 제대로 공부할 때가 된 것 같다.