LeetCode 30 - Substring with Concatenation of All Words

https://leetcode.com/problems/substring-with-concatenation-of-all-words

 

문자열 s, 같은 길이의 단어가 들어있는 String [] words

concatenated string이라는 것이 등장한다. 이는 words의 단어들을 순열로 만들어 하나로 합친 것들이다.

예를 들면 words = [”ab”, “cd”, “ef”] 일 때 이 배열의 순열들은 다음과 같다.

[”ab”, “cd”, “ef”], [”ab”, “ef”, “cd”], [”cd”, “ab”, “ef”], [”cd”, “ef”, “ab”], [”ef”, “ab”, “cd”], [”ef”, “cd”, “ab”] 이렇게 총 6가지이다.

따라서 concatenated string은 다음의 6가지가 된다.

“abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd”, “efcdab”

문자열 S에서 모든 concatenated string의 substring 위치를 담은 리스트를 반환하라.

 

substring의 위치 같은 경우에는 indexOf를 사용하면 찾을 수 있을 것 같다.

결국 필요한 것은 words의 단어들로 순열을 만들어 concatenated string를 구성하는 것이다.

주의할 점은 words 내에 똑같은 단어가 여러 번 등장할 수 있다는 것이다.

이렇게 되면 순열을 구성시에 중복된 concatenated string이 등장할 수 있다. 따라서 중복처리가 필요하다.

중복처리는 그냥 간단하게 Set을 통해 처리하겠다.

또 다른 문제도 있다. 문자열 s에서 같은 substring이 2번 등장했을 때이다. indexOf는 처음으로 등장하는 substring(부분 문자열)의 index만을 반환한다.

이를 해결하려면 substring의 위치를 판단하는 메서드를 새롭게 작성하던가 indexOf 중 오버로딩 된 시작 위치를 변경해 가며 찾는 메서드를 사용하는 방식이 있다. 나는 후자를 선택했다.

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Set<Integer> answer = new HashSet<>();
        permutation(0, words, new boolean[words.length], new StringBuilder(), answer, s);
        return answer.stream().collect(Collectors.toList());
    }

    private void permutation(int idx, String[] words, boolean[] visited, StringBuilder sb, Set<Integer> answer, String s) {
        if (idx == words.length) {
            // 마지막 위치까지 확인
            int from = 0;
            while (from < s.length()) {
                int substringIdx = s.indexOf(sb.toString(), from);
                if (substringIdx == -1) {
                    break;
                }
                answer.add(substringIdx);
                from = substringIdx + 1;
            }
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            permutation(idx + 1, words, visited, new StringBuilder(sb.toString()).append(words[i]), answer, s);
            visited[i] = false;
        }
    }
}    

시간초과가 발생했다.

s = "fffffffffffffffffffffffffffffffff”

words = ["a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"]

이 경우에서 실패했다.

그냥 위의 생각 자체가 틀렸다. 문제의 조건을 다시 보자. words 배열의 최대 길이는 5000이다.

그렇게 되면 만들어지는 수열은 최대 5000! 이 된다. 이는 절대로 위의 방식으로는 풀 수 없는 수치이다.

또한 indexOf로 substring을 검색하는 방식도 s가 길어질수록 비효율적으로 변한다.

 

다른 방식을 생각해 보자.

사용하지 않은 조건 중에 words의 모든 단어가 같은 길이를 갖는다는 조건이 있다.

여기서 얻을 수 있는 정보는 유효한 substring의 길이가 항상 일정하다는 것이다.

일정한 크기의 슬라이딩 윈도인가? 하는 생각이 든다.

또한 words의 모든 단어가 1번씩은 등장한다는 조건도 있다.

 

이를 통해서 생각을 정리해 보자.

해당 슬라이딩 윈도 크기 내에서 등장하는 words의 단어들의 빈도수를 알면 된다.

예를 들어 words = [”foo”, “bar”, “foo”] 이면 “foo”가 2번, “bar”가 1번 등장해야만 한다.

슬라이딩 윈도를 이동해 가면서 해당 범위 내에서 “foo”가 2번, “bar”가 1번 등장했는지 확인만 하면 된다.

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> answer = new ArrayList<>();
        Map<String, Integer> wordsMap = new HashMap<>();
        int size = words[0].length();
        int windowSize = words.length * size;
        
        for (String word : words) {
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }

        int left = 0;
        for (int right = windowSize; right <= s.length(); right++) {
            String substring = s.substring(left, right);
            // substring을 size(단어 길이) 단위로 분할
            int start = 0;
            Map<String, Integer> substringWordMap = new HashMap<>();
            while (start < substring.length()) {
                String word = substring.substring(start, start + size);
                substringWordMap.put(word, substringWordMap.getOrDefault(word, 0) + 1);
                start += size;
            }
            if (wordsMap.equals(substringWordMap)) answer.add(left);

            left++;
        } 
        
        return answer;
    }
}

정답은 통과됐다. 그런데 시간 효율이 엄청나게 별로다.

가장 좋은 시간 효율을 가진 사람에 비해 터무니없이 느리다.

 

여기서부터는 당장 개선 방법이 안 떠오르므로 gpt의 도움을 받아 정답 코드를 분석해 보자.

import java.util.*;

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s == null || s.length() == 0 || words == null || words.length == 0) return result;
        
        int wordLength = words[0].length();
        int totalLength = wordLength * words.length;
        
        // 단어 빈도 맵 생성
        Map<String, Integer> wordCount = new HashMap<>();
        for(String word : words){
            wordCount.put(word, wordCount.getOrDefault(word, 0) +1);
        }
        
        // 단어 길이만큼 이동하며 검사
        for(int i = 0; i < wordLength; i++){
            int left = i, right = i, count = 0;
            Map<String, Integer> currentCount = new HashMap<>();
            while(right + wordLength <= s.length()){
                String word = s.substring(right, right + wordLength);
                right += wordLength;
                if(wordCount.containsKey(word)){
                    currentCount.put(word, currentCount.getOrDefault(word, 0) +1);
                    count++;
                    
                    // 빈도 초과시 왼쪽 포인터 이동
                    while(currentCount.get(word) > wordCount.get(word)){
                        String leftWord = s.substring(left, left + wordLength);
                        currentCount.put(leftWord, currentCount.get(leftWord) -1);
                        left += wordLength;
                        count--;
                    }
                    
                    // 모든 단어 매칭시 결과에 추가
                    if(count == words.length){
                        result.add(left);
                    }
                } else {
                    // 일치하지 않는 단어일 경우 초기화
                    currentCount.clear();
                    count = 0;
                    left = right;
                }
            }
        }
        return result;
    }
}

위의 코드는 엄청나게 빠르다. 기존의 방식과 뭐가 차이나길래 이렇게 속도차이가 날까?

 

외부 루프가 한 단어의 길이만큼만 반복하고 있다.

이 내부에서 슬라이딩 윈도를 사용해 문자열 s를 검사하는 방식을 쓴다.

하지만 내 코드 같은 경우에는 외부 루프가 1씩 증가하며 모든 지점을 검사하고 있다.

슬라이딩 윈도가 유의미하게 사용된 곳이 없다.

한 단어의 길이만큼 반복해도 모든 가능한 위치에서 검사할 수 있는 이유는 단어들이 모두 같은 길이를 가지기 때문이다.

예를 들어 한 단어가 “foo” 이면

i = 0 일 때는 0, 3, 6, 7, 12를 시작 인덱스로 검사하고

i = 1 일 때는 1, 4, 7, 10, 13 i = 2 일 때는 2, 5, 8, 11, 14가 된다.

 

솔직히 실제 상황에서 이렇게 풀라 하면 못 풀 것 같다.