[프로그래머스/카카오 블라인드 테스트 2020/java] 가사검색

 

코드

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        for(int i=0;i <answer.length ; i++){
            answer[i] = 0;
        }
        
        int queryIdx = 0;
        for(String query : queries){
            int firstIdx = getFirstIdx(query);
            int queryLen = query.length();
            query = query.replaceAll("\\?", "");
            for(String word : words){
                int matchingIdx = word.indexOf(query, firstIdx);
               
                if(matchingIdx == firstIdx && word.length() == queryLen){
                    answer[queryIdx] += 1;
                }
                
            } queryIdx++;
        }
        return answer;
    }
    
    public int getFirstIdx(String query){
        for(int i=0; i<query.length(); i++){
            if(query.charAt(i) != '?'){
                return i;
            } 
        }
        return -1;
    }
}

근데 시간초과가 떴다.. 심지어 효율성 테스트 5개 중에서 3개나 흙흙..

다시 효율성을 생각해서 자세히보니

indexOf()의 time complexity가 무려 O(n^2).. ㅎㄷㄷ 좋은 놈인줄 알았는데 아니었엉

 

그래서...! 비교시간을 n으로 줄여주고자

isMatched()라는 함수를 새로 만들어서 char끼리 각각 비교해줬다

처음에는 substring으로 해보려했는데 string concat하는데 시간이 좀 걸릴 것같아서 char 하나하나씩 비교해줬다

그리고 if(word.length() == queryLen && isMatched())에서 둘을 놓고 봤을 때, isMatched()의 비용이 더 높아서 length 비교를 먼저 해주었다. 애초에 length가 다르면 꽝이기 때문에 isMatched() 를 수행하는 의미가 없어지기 때문이다.

 

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public int[] solution(String[] words, String[] queries) {
        int[] answer = new int[queries.length];
        for(int i=0;i <answer.length ; i++){
            answer[i] = 0;
        }
        
        int queryIdx = 0;
        for(String query : queries){
            int firstIdx = getFirstIdx(query);
            int queryLen = query.length();
            query = query.replaceAll("\\?", "");
            for(String word : words){
                if( word.length() == queryLen 
                   && isMatched(word, query, firstIdx)){
                    answer[queryIdx] += 1;
                }
                
            } queryIdx++;
        }
        return answer;
    }
    public boolean isMatched(String word, String query, int idx){
        int lastIdx = query.length();
        for(int i =0; i<query.length(); i++){
            if(word.charAt(idx+i) != query.charAt(i))
                return false;
        }
       return true;
    }
    
    public int getFirstIdx(String query){
        for(int i=0; i<query.length(); i++){
            if(query.charAt(i) != '?'){
                return i;
            } 
        }
        return -1;
    }
}

하지만 똑같은 결과가 뚜뚱... 뭔가 속도는 좀 더 향상된 것같지만 여전히 시간초과가 나는 부분들은 변하지 않았다.

방법을 아예 바꿔야하는 건가..

 

내일 더 생각해보도록하자