[탐색] O(N^2) / 긴 문자열 내 짧은 문자열 탐색

배열 내 문자열을 탐색하는 무식한 방법이다.

 

알고리즘이 기억이 안날 경우, Naive한 방법으로도 해결이 가능해야하므로

해당 글을 포스팅한다.

 

문제는 아래와 같다.

---

 

/*
인수로 문자열 2개를 가지는 naivestring이라는 함수를 작성해라.
첫번째 인수로 들어가는 문자열 내부에 
두번째 인수로 들어가는 문자열이 총 몇개가 있는지 카운트해서 리턴한다.
*/

naivestring('멋쟁이사자처럼', '이사자') // 1
naivestring('안녕하세요감사해요잘있어요다시만나요', '요') // 4
naivestring('디아블로', '메피스토') // 0

 

 

풀이 전 생각)

• for문을 사용해서 해결한다.
• 일단 count 변수를 하나 생성해서 for문이 다 끝나면 리턴한다.
• 외부 for문을 첫번째 인수 문자열을, 내부 for문은 두번째 인수 문자열을 순회한다.
• 외부 for문의 인덱스 카운터는 i, 내부 for문의 인덱스 카운터는 j로 한다.
• 각 문자열을 비교하며, 정답 조건에 맞는 상황이 있으면 카운터를 하나씩 증가시킨다.
• j는 계속 반복해서 시작하지만, i는 천천히 하나씩 순회하므로 이를 잘 생각하고 알고리즘을 짠다.

 

 

풀이)

function naivestring(str, short) {
    let count = 0
    for(let i = 0; i < str.length; i++) {       // (1)
        for(let j = 0; j < str.length; j++) {   // (2)
            if(short[j] !== str[i + j]) break   // (3)
            if(j === short.length - 1) count++  // (4)
        } 
    }
    return count                                // (5)
}


/*
(1) 외부 for문으로 긴 문자열을 순회한다.
(2) 내부 for문으로 짧은 문자열을 순회한다.
(3) j는 언제나 초기에 시작할 때 0으로 시작한다. 
    긴 문자열과 짧은 문자열을 비교하려면 i + j를 해줘야 긴 문자열의 다음 인덱스를 확인할 수 있다.
    만약 짧은 문자열 내 엘리먼트와 긴 문자열 내 엘리먼트가 다르다면 내부 순회를 break한다.
(4) 이상없이 다 순회했다면 문자열이 같았다는 의미가 되므로 count를 증가시킨다.
(5) 내부 순회가 끝나면 count를 리턴한다.
*/