Programmers - 가사 검색 with JAVA

 

 

첫번째 시도

1. 단어들에 대해서 길이에 따른 해시맵 생성

2. 뒤집은 단어들을 길이에 따라 해시맵 생성

3. 쿼리마다 ?로 시작하는지 여부에 따라 첫번째 해시맵 또는 두번째 해시맵 불러온다.

4. 불러온 List에서 ?를 제외한 쿼리로 시작하는 단어의 개수를 구한다.

 

문제점

4번에서 모든 단어들을 하나씩 불러오기에는 시간복잡도에 문제가 생긴다.

 

 

 

두번째 시도

- 단어들에 대해서 길이에 따른 해시맵 생성

- 뒤집은 단어들을 길이에 따라 해시맵 생성

- 해시맵 정렬

- 쿼리마다 ?로 시작하는지 여부에 따라 첫번째 해시맵 또는 두번째 해시맵 불러온다.

- ?를 a로 대체한 String, z로 대체한 String 두개 생성

- a로 대체한 String이 들어갈 위치와 z로 대체한 String이 들어갈 위치 구하고 차이로 범위안에 있는 String의 수를 구한다.

 

 

결론

- left_index, right_index 함수 암기

- compareTo 로 String 비교시 헷갈리지 않게 정리하자

 

 

 

1차 코드

 

import java.util.*;
class Solution {
    public int[] solution(String[] words, String[] queries) {
        int n = queries.length;
        int[] answer = new int[n];
        HashMap<Integer, List<String>> map = new HashMap<>();
        HashMap<Integer, List<String>> re_map = new HashMap<>();
        for(String word : words){ 
            int len = word.length();
            StringBuilder sb = new StringBuilder(word);
            String re_word = sb.reverse().toString();
            if(map.get(len) == null){
                List<String> now = new ArrayList<>();
                now.add(word);
                map.put(len, now);
            }
            else{
                List<String> now = map.get(len);
                now.add(word);
                map.put(len, now);
            }
            if(re_map.get(len) == null){
                List<String> now = new ArrayList<>();
                now.add(re_word);
                re_map.put(len, now);
            }
            else{
                List<String> now = re_map.get(len);
                now.add(re_word);
                re_map.put(len, now);
            }
        }
        for(int i=0; i<n; i++){
            String query = queries[i];
            int len = query.length();
            if(query.charAt(0) == '?'){
                List<String> check = re_map.get(len);
                if(check == null){
                    continue;
                }
                StringBuilder value = new StringBuilder();
                for(int j=len-1; j>=0; j--){
                    char c = query.charAt(j);
                    if(c == '?'){
                        break;
                    }
                    value.append(c);
                }
                String result = value.toString();
                for(String now : check){
                    if(now.startsWith(result)){
                        answer[i] += 1;   
                    }
                }
            }
            else{
                List<String> check = map.get(len);
                if(check == null){
                    continue;
                }
                StringBuilder value = new StringBuilder();
                for(char c : query.toCharArray()){
                    if(c == '?'){
                        break;
                    }
                    value.append(c);
                }
                String result = value.toString();
                for(String now : check){
                    if(now.startsWith(result)){
                        answer[i] += 1;   
                    }
                }
            }
        }
        return answer;
    }
}

 

 

 

2차 코드

 

import java.util.*;
class Solution {
    public int[] solution(String[] words, String[] queries) {
        
        // 정답 배열
        int n = queries.length;
        int[] answer = new int[n];
        
        // 길이별 해시 함수 만들기
        HashMap<Integer, List<String>> or_map = new HashMap<>();
        HashMap<Integer, List<String>> re_map = new HashMap<>();
        for(String word : words){
            int len = word.length();
            if(or_map.get(len) == null){
                List<String> now = new ArrayList<>();
                now.add(word);
                or_map.put(len, now);
            }
            else{
                List<String> now = or_map.get(len);
                now.add(word);
                or_map.put(len, now);
            }
            StringBuilder sb = new StringBuilder(word);
            String re_word = sb.reverse().toString();
            if(re_map.get(len) == null){
                List<String> now = new ArrayList<>();
                now.add(re_word);
                re_map.put(len, now);
            }
            else{
                List<String> now = re_map.get(len);
                now.add(re_word);
                re_map.put(len, now);
            }
        }
        
        // 정렬
        for(int key : or_map.keySet()){
            List<String> values1 = or_map.get(key);
            List<String> values2 = re_map.get(key);
            Collections.sort(values1);
            Collections.sort(values2);
            or_map.put(key, values1);
            re_map.put(key, values2);
        }
        
        // 메인로직
        for(int i=0; i<n; i++){
            String query = queries[i];
            int len = query.length();
            // ?로 시작하는 경우
            if(query.charAt(0) != '?'){
                String start = query.replace("?", "a");
                String end = query.replace("?", "z");
                List<String> array = or_map.get(len);
                if(array == null){
                    continue;
                }
                answer[i] = find(array, start, end);
            }
            // ?로 시작하지 않는 경우
            else{
                StringBuilder sb = new StringBuilder(query);
                String re_query = sb.reverse().toString();
                String start = re_query.replace("?", "a");
                String end = re_query.replace("?", "z");
                List<String> array = re_map.get(len);
                if(array == null){
                    continue;
                }
                answer[i] = find(array, start, end);
            }
        }
        return answer;
    }
    public static int find(List<String> array, String start, String end){
        int left = left_index(array, start);
        int right = right_index(array, end);
        return right-left;
    }
    public static int right_index(List<String> arr, String target){
        int start = 0;
        int end = arr.size();
        while(start<end){
            int mid = (start+end)/2;
            String value = arr.get(mid);
            // arr[mid]가 target보다 사전순으로 같거나 뒤에 있다면
            if(value.compareTo(target) >= 0){
                end = mid;   
            }
            else{
                start = mid+1;   
            }
        }
        return end;
    }
    public static int left_index(List<String> arr, String target){
        int start = 0;
        int end = arr.size();
        int result = 0;
        while(start<end){
            int mid = (start+end)/2;
            String value = arr.get(mid);
            // arr[mid]가 target보다 사전순으로 뒤에 있다면
            if(value.compareTo(target) > 0){
                end = mid;
            }
            else{
                start = mid+1;   
            }
        }
        return end;
    }
}