이진탐색 - 가사 검색(프로그래머스) - Java

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/60060

2. 풀이

참고 풀이:
https://github.com/ndb796/python-for-coding-test/blob/master/15/4.java

 
해당 풀이는 아래 유형으로
https://velog.io/@minkang911/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-3.-%EC%A4%91%EB%B3%B5%EB%90%98%EB%8A%94-%EA%B0%92%EB%93%A4-%EB%AA%87%EA%B0%9C-%EB%82%98%EC%98%A4%EB%8A%94%EC%A7%80-%EC%B0%BE%EA%B8%B0
이진탐색으로 lowerBound와 upperBound를 찾아 조건에 맞는게 몇개가 되는지 찾는 문제이다.

2-1. ✨핵심 Point

 

String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?"};

0. ?가 접두사로 등장할경우를 위해 기존 단어를 뒤집은 단어를 담고 있는 리스트를 별도로 선언.

ArrayList<ArrayList<String>> list = new ArrayList<>();
ArrayList<ArrayList<String>> reverseList = new ArrayList<>();
for(int i = 0; i <= 10000; i++) {
	list.add(new ArrayList<>());
	reverseList.add(new ArrayList<>());
}

1. 각 단어를 길이에 따라서 나눈다.

   길이가 5인 단어 리스트: ["frodo", "front", "frost", "frame", "kakao"]
   길이가 6인 단어 리스트: ["frozen"]

for(String word : words) {
	list.get(word.length()).add(word);
	reverseList.get(word.length()).add(new StringBuffer(word).reverse().toString());
}

2. (제일 중요) 각 길이의 리스트를 (알파벳 순서로)정렬한다.
   정렬은 이진탐색의 기본이다!

for(int i = 0; i <= 10000; i++) {
	Collections.sort(list.get(i));
	Collections.sort(reverseList.get(i));
}

3. ?가 먼저 오는 문자의 경우 reverseList를 탐색한다.

3. 코드

import java.util.*;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        
        ArrayList<ArrayList<String>> list = new ArrayList<>();
        ArrayList<ArrayList<String>> reverseList = new ArrayList<>();
        
        for(int i = 0; i <= 10000; i++){
            list.add(new ArrayList<>());
            reverseList.add(new ArrayList<>());
        }
        
        for(String word : words){
            list.get(word.length()).add(word);
            reverseList.get(word.length()).add(new StringBuffer(word).reverse().toString());
        }
        
        //가장 중요한 것
        for(int i = 0; i <= 10000; i++){
            Collections.sort(list.get(i));
            Collections.sort(reverseList.get(i));
        }
        
        for(int i = 0; i < queries.length; i++){
            String query = queries[i];
            int res = 0;
            
            if(query.charAt(0) == '?') {
                query = new StringBuffer(query).reverse().toString();
                res = countByRange(reverseList.get(query.length()), query.replaceAll("\\?", "a"), query.replaceAll("\\?", "z"));
            } else {
                res = countByRange(list.get(query.length()), query.replaceAll("\\?", "a"), query.replaceAll("\\?", "z"));
            }
            
            answer[i] = res;
            
        }
        
        return answer;
    }
    
    public int countByRange(ArrayList<String> arr, String leftValue, String rightValue){
        
        int rightIndex = upperBound(arr, rightValue, 0, arr.size());
        int leftIndex = lowerBound(arr, leftValue, 0, arr.size());
            
        return rightIndex - leftIndex;
    }
    
    public int upperBound(ArrayList<String> arr, String target, int start, int end){
        while(start < end){
            int mid = (start + end) / 2;
            
            if(arr.get(mid).compareTo(target) >= 0){
                end = mid;
            } else {
                start = mid+1;
            }
        }
        return start; // return end도 가능
    }
    
    public int lowerBound(ArrayList<String> arr, String target, int start, int end){
        while(start < end){
            int mid = (start + end) / 2;
            
            if(arr.get(mid).compareTo(target) > 0){
                end = mid;
            } else{
                start = mid + 1;
            }
        }
        return start; // return end도 가능
    }
}