[ 프로그래머스 / Javascript ] 문자열안에 문자열

https://school.programmers.co.kr/learn/courses/30/lessons/120908

프로그래머스

 

 

문제 설명

---

문자열 str1, str2가 매개변수로 주어집니다. str1 안에 str2가 있다면 1을 없다면 2를 return하도록 solution 함수를 완성해 주세요.

 

 

제한사항

---

• 1 ≤ str1의 길이 ≤ 100
• 1 ≤ str2의 길이 ≤ 100
• 문자열은 알파벳 대문자, 소문자, 숫자로 구성되어 있습니다.

 

 

입출력 예

---

str1 str2 result

str1	str2	result
"ab6CDE443fgh22iJKlmn1o"	"6CD"	1
"ppprrrogrammers"	"pppp"	2
"AbcAbcA"	"AAA"	2

 

 

입출력 예 설명

---

입출력 예 #1

• "ab6CDE443fgh22iJKlmn1o" str1에 str2가 존재하므로 1을 return합니다.

입출력 예 #2

• "ppprrrogrammers" str1에 str2가 없으므로 2를 return합니다.

입출력 예 #3

• "AbcAbcA" str1에 str2가 없으므로 2를 return합니다.

 

 

나의 풀이

---

나의 풀이가 통과는 했지만 시간 복잡도에서는 효율적이지 못하다.

 

코드 동작 방식

이 코드는 str1을 한 글자씩 순회하면서 str2의 첫 글자와 같은 곳을 찾고, 그 위치에서 str2.length 만큼 잘라 str2와 비교하는 방식으로 동작합니다.

function solution(str1, str2) {
    for (let i = 0; i < str1.length; i++) { // (1) str1을 처음부터 끝까지 순회
        if (str1[i] === str2[0]) {          // (2) str2의 첫 글자와 같은 곳을 찾음
            let currStr = str1.substring(i, i + str2.length); // (3) 해당 위치에서 str2 길이만큼 잘라서 비교
            if (currStr === str2) { // (4) 일치하면 1 반환
                return 1;
            }
        }
    }
    return 2; // 찾지 못하면 2 반환
}

 

⏳ 시간 복잡도 분석

1. for 루프가 str1.length = N 만큼 실행됨 → O(N)

2. str1.substring(i, i + str2.length) 실행 → O(M) (M = str2.length)

3. substring()으로 잘라낸 문자열과 str2를 비교하는 부분 → O(M)

(최악의 경우, str1의 거의 끝에서 str2를 찾게 되면, 최대 N번 수행)

 

💡 총 시간 복잡도

• 최악의 경우 O(NM) → str1에서 N번 순회하면서 substring()에서 M번 연산 수행

 

 

더 효율적인 방법

---

현재 코드보다 효율적인 방법은 크게 3가지가 있다.

 

1. includes() 사용 (더 간단한 방법)

• JavaScript의 includes() 메서드를 사용하면 훨씬 간단하고 가독성이 좋다.

function solution(str1, str2) {
    return str1.includes(str2) ? 1 : 2;
}

⏳ 시간 복잡도: O(N) (일반적인 구현에서 includes()는 내부적으로 indexOf()와 비슷하게 최적화되어 있다.)

 

 

2. indexOf() 사용 (더 빠름)

• indexOf()를 사용하면 substring()을 반복적으로 실행하는 것보다 효율적입니다.

function solution(str1, str2) {
    return str1.indexOf(str2) !== -1 ? 1 : 2;
}

⏳ 시간 복잡도: O(N)

 

 

3. split()을 사용

• split()은 내부적으로 전체 문자열을 탐색하면서 str2를 찾고 나누는 연산을 수행.

• 문자열을 한 번 끝까지 순회해야 하므로, 최악의 경우 O(N) (N = str1.length)

• 하지만, split()은 str2가 몇 번 등장하는지도 체크해야 하므로 일반적인 indexOf()보다는 약간 느릴 수 있음.

  (이유: split()은 찾기만 하는 게 아니라 배열을 생성하는 추가 작업이 있기 때문)

function solution(str1, str2) {
    return str1.split(str2).length > 1 ? 1 : 2;
}

⏳ 시간 복잡도 분석: O(N)

 

방법	시간 복잡도	비고
기존 코드 (for + substring())	O(NM)	문자열이 길 경우 비효율적
includes() (추천)	O(N)	가장 간단하고 가독성 좋음. 하지만 내부적으로 최적화되어 있지만 보장된 최적 시간은 아님
indexOf() (추천)	O(N)	빠르고, 내부적으로 최적화됨
split()	O(N)	indexOf()보다 조금 더 느릴 수 있음 (배열 생성 때문)

 

 

결론: 어떤 방법이 가장 좋을까?

---

• includes() 또는 indexOf() 사용 (간단하고 빠름!)