[99클럽 코테 스터디 15일차 TIL] Prefix and Suffix Search - Java [자바][Leetcode]

 

 

📜 문제 내용

좌) 원문 문제 , 우) DeepL 번역본

 

🤔 과정

• 접두사와 접미사를 기준으로 단어를 찾게 하고, 가장 큰 인덱스를 반환시켜야한다. 
• 그래서 문자열을 자르는 substring을 이용해 HashMap 안에 문자열을 자른 접두사와 접미사 조합으로 key를 생성하고, value 값으로 인덱스를 넣으면 가장 큰 값이 자동으로 덮여진다는 점을 이용. 

 

✨ 최초 제출 답안

class WordFilter {
    private final HashMap<String, Integer> mapPrefSuff;


    public WordFilter(String[] words) {
        mapPrefSuff = new HashMap<>();

        for(int i = 0; i < words.length; i++){
            String word = words[i];
			
            // substring(0, j) : 문자열의 0 번 인덱스부터 j-1까지의 문자열 자르기
            for(int j = 0; j <= word.length(); j++){
                String pref = word.substring(0, j);
                
                // substring(k) : 문자열의 k 번 인덱스부터 끝까지 문자열 자르기 
                for(int k = 0; k <= word.length(); k++){
                    String suff = word.substring(k);

                    mapPrefSuff.put(pref + "&" + suff, i);
                }
            }
        }

    }

    public int f(String pref, String suff) {
        String key = pref + "&" + suff;

        return mapPrefSuff.getOrDefault(key, -1);
    }
}    


/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */

최초 코드 결과

• 첫 제출 시, substring의 인덱스 착각 이슈로 j < word.length() , k < word.length() 로 해버리는 바람에 한 글자 문자열에 대한 처리가 되지 않았다. 그래서 j <= word.length() , k <= word.length() 로 하자, Accepted 는 되었다. 
• 하지만, 위의 코드로 작성하면 "apple" 이라는 문자열로 map에 넣으면, "appl&pple" 같이 "ppl" 부분이 겹치는 오류를 범할 수 있다. 그래서 접두사, 접미사에 대한 정의에 맞지 않게 할 뿐더러, 무의미한 비용이 들 것이라고 생각해서 코드를 재작성해봤다. 

 

✍️ 재제출 답안

class WordFilter {
    // 접두사와 접미사가 맵핑될 HashMap 
    private final HashMap<String, Integer> mapPrefSuff;

    public WordFilter(String[] words) {
        mapPrefSuff = new HashMap<>();

        for(int idx = 0; idx < words.length; idx++){
            String word = words[idx];
            
            // 한 단어 처리할 때마다 접두, 접미 그룹을 따로 생성
            ArrayList<String> groupPref = new ArrayList<>();
            ArrayList<String> groupSuff = new ArrayList<>();
            
            // 한 단어를 잘라서 앞과 뒤를 따로 저장
            for(int j = 0; j <= word.length(); j++){
                String pref = word.substring(0,j);
                String suff = word.substring(j);

                groupPref.add(pref);
                groupSuff.add(suff);
            }
            
            // 모든 접두사와 접미사를 &로 붙여 맵핑 추가 
            // 단어 번호가 idx 
            for(String pref : groupPref){
                for(String suff : groupSuff){
                    mapPrefSuff.put(pref + "&" + suff, idx);
                }
            }
        }

    }
    
    // 접두사와 접미사가 들어왔을 때, 
    // 맞는게 있으면 단어번호 idx 반환, 없으면 -1 반환
    public int f(String pref, String suff) {
        String key = pref + "&" + suff;

        return mapPrefSuff.getOrDefault(key, -1);
    }
}    


/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */

재제출 코드 결과

• 아주 미세하게 Runtime이 줄었지만, 엄청 크지는 않은 결과가 나왔다. 
• 다른 사람의 풀이를 보니, Trie를 이용한 풀이가 효율성 측면에서 더 적합한 것 같다. 
• LeetCode는 처음인데, 개인적으로 백준과 프로그래머스보다 훨씬 개발하는 느낌이 들게 문제를 주고 풀이하게 돼서 색다른 느낌이 들었다. 

 

🔗 문제 링크

• LeetCode - 745. Prefix and Suffix Search (링크)