Substring with Concatenation of All Words

💬 문제

[문제 링크]

같은 길이의 단어들이 들어있는 배열 words
문자열 s에 words를 조합한 문자열이 존재하면
그 위치의 시작 인덱스를 담아서 배열로 반환
words의 모든 단어가 들어가야하며, 순서는 상관 없음

✍️ 나의 풀이

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let res = [];
    let wordLen = words[0].length;
    let subLen = wordLen * words.length;

    for (let i = 0; i < s.length - subLen + 1; i++) {
        let check = s.slice(i, i + subLen);
        let split = new Map();
        for (let j = 0; j < check.length; j += wordLen) {
            let tmp = check.slice(j, j + wordLen);
            split.has(tmp) ? split.set(tmp, split.get(tmp) + 1) : split.set(tmp, 1);
        }
        let k = 0;
        for (k; k < words.length; k++) {
            if (!split.has(words[k]))
                break ;
            if (split.get(words[k]) === 1)
                split.delete(words[k]);
            else
                split.set(words[k], split.get(words[k]) - 1);
        }
        if (k === words.length)
            res.push(i);
    }

    return res;
};

wordLen은 단어의 길이 (모든 단어가 같은 길이를 가짐)
subLen은 모든 단어를 합쳤을 때의 문자열 길이
s를 한칸씩 순회하면서 시작 (적어도 wordLen 만큼씩 증가하고 싶었으나 s는 words 내의 단어 외에도 다른 문자가 랜덤으로 들어있음)
모든 단어가 들어있는 부분 문자열을 찾기 때문에 조건식은 subLen을 뺀 인덱스까지만 확인 하는 걸로
우선 현재 위치에서 subLen까지 잘라서 그 문자열을 확인 (check)
split이라는 맵에 wordLen 만큼씩 다시 잘라서 저장
중복 단어가 있을 수 있으므로 이미 해당 단어를 저장했다면 값을 증가
이제 words를 돌면서 split 맵 안에 해당 단어가 들어있는 지 확인
있으면 제거 (중복 단어라면 값 -1) 없으면 부분 문자열이 성립되지 않으므로 반복문 중단
모든 문자를 확인했으면 현재 인덱스 위치 (check 문자열의 시작점이었던) 저장

📌 결과

Accepted
Runtime 1623ms (Beats 20.74%)
Memory 56.73MB (Beats 82.44%)

📚 러닝 포인트

역시 hard 문제여서 그런지 확실히 어려웠다. 혼자서 풀 때는 배열과 문자열로만 해결하려고 하다가 특정 테스트 케이스에서 시간 초과가 나버렸다. 그렇게 솔루션을 둘러보니 대부분 map을 사용하는 것이 보였고 확실히 배열보다는 map이 검색 속도가 빠르기 때문에 split 부분을 배열로 바꿨더니 통과했다. 그럼에도 런타임 효율은 그다지 좋지 않았는데, 아마 다른 사람들은 words 자체도 map에 따로 저장해두기 때문에 조금 더 빠른 것 같다. 이번 문제를 풀면서 왜 그렇게 사람들이 map을 자꾸 사용하는지 체감이 되기 시작했다. 워낙 자바스크립트로는 문자열이랑 배열에 익숙해져 있어서 웬만하면 그걸 사용하려고 하는데 map의 이점을 잘 파악하고 연습하는 것도 필요할 것 같다는 생각이 든다.