[프로그래머스] 연습문제 / 크기가 작은 부분 문자열 / Lv1 / JS

 

---

문제 설명

문제 설명

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서,

이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.

예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

---

제한사항

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

t	p	result
"3141592"	"271"	2
"500220839878"	"7"	8
"10203"	"15"	3

나의 접근 방법

1. 반복문을 통해서 비교해서 count를 체크한다.

2. 반복문은 t 길이 - p 길이 만큼 반복하면서 p 값과 비교한다.

나의 JS 코드

function solution(t, p) {
    var answer = 0;
    for(let i=0; i<=t.length-p.length; i++){
        if(Number(t.slice(i,i+p.length)) <= Number(p)){
            answer += 1;
        }
    }
    return answer;
}

개선할 포인트

1. 불필요한 Number 변환 최소화 : 현재 코드는 반복문 내부에서 매번 Number()를 호출하여 문자열을 숫자로 변환하고 있습니다. p는 고정된 숫자이므로, 반복문 시작 전에 한 번만 변환하면 성능이 약간 개선됩니다.

 

2. 동적 프로그래밍 및 사전 계산 : 만약 주어진 문자열 t가 매우 길고 여러 쿼리(p)를 처리해야 한다면, 모든 p에 대해 부분 문자열 비교를 반복하는 대신, 사전 계산을 통해 성능을 최적화할 수 있습니다. 이는 문자열 t의 모든 길이별 부분 문자열을 미리 숫자로 변환하여 저장하는 방식입니다.

최악의 시간 복잡도

코드의 시간 복잡도는 O(n * m)입니다:

• n: 문자열 t의 길이 (최대 10,000)
• m: 문자열 p의 길이 (최대 18)

즉, 최악의 경우 약 180,000회 연산이 필요합니다.

성능 최적화 포인트:

• t와 p가 매우 길 경우, 숫자 변환(Number 또는 BigInt) 대신 문자열 비교를 사용합니다.
• 연산량을 줄이기 위해 미리 처리 가능한 부분(예: 범위 확인)을 필터링할 수 있습니다.

 

개선 된 코드

 

장점:

• Number() 변환 비용이 없으므로 더 빠르게 수행됩니다.
• 숫자 범위(특히 길이가 긴 경우)가 클 때도 안정적으로 동작합니다.

단점:

• 숫자 표현이 아닌 사전 순서로 비교하므로, 숫자로 해석했을 때와 결과가 다를 수 있습니다.
  • 예: "001" vs "1" → 문자열 비교는 "001" > "1"로 판단, 숫자 비교는 1 === 1로 판단.

function solution(t, p) {
    let answer = 0;
    const pLength = p.length;

    for (let i = 0; i <= t.length - pLength; i++) {
        // 문자열로 직접 비교
        if (t.slice(i, i + pLength) <= p) {
            answer++;
        }
    }
    return answer;
}

속도 체크

 

• 개선 전 -> 숫자 비교:
  • Number() 변환이 필요하므로 약간의 추가 연산 비용이 발생합니다.
  • 비교는 정확하지만, 변환 과정에서 상대적으로 느립니다.
  • 특히 t.length가 매우 크고 반복문이 많을 때 성능 병목이 될 수 있습니다.
• 개선 후 -> 문자열 비교:
  • Number() 변환이 없으므로 더 빠릅니다.
  • 문자열을 그대로 비교하므로 메모리를 추가로 사용하지 않습니다.
  • 다만, 숫자 비교와 동일한 결과가 보장되지 않는 상황에 유의해야 합니다.

 

케이스	개선 전	개선 후
테스트 1 〉	통과 (0.63ms, 33.8MB)	통과 (0.24ms, 33.6MB)
테스트 2 〉	통과 (2.70ms, 37.1MB)	통과 (0.83ms, 33.3MB)
테스트 3 〉	통과 (2.34ms, 36.6MB)	통과 (2.15ms, 36.6MB)
테스트 4 〉	통과 (0.66ms, 33.6MB)	통과 (0.40ms, 33.3MB)
테스트 5 〉	통과 (0.63ms, 33.5MB)	통과 (0.28ms, 33.6MB)
테스트 6 〉	통과 (2.33ms, 36.8MB)	통과 (2.13ms, 36.7MB)
테스트 7 〉	통과 (4.04ms, 37.1MB)	통과 (2.37ms, 36.8MB)
테스트 8 〉	통과 (0.66ms, 33.6MB)	통과 (0.36ms, 33.5MB)
테스트 9 〉	통과 (0.41ms, 33.5MB)	통과 (0.21ms, 33.4MB)
테스트 10 〉	통과 (0.15ms, 33.6MB)	통과 (0.13ms, 33.4MB)
테스트 11 〉	통과 (0.97ms, 33.7MB)	통과 (0.43ms, 33.5MB)
테스트 12 〉	통과 (4.30ms, 37.1MB)	통과 (2.36ms, 36.8MB)
테스트 13 〉	통과 (1.57ms, 33.8MB)	통과 (0.68ms, 33.8MB)
테스트 14 〉	통과 (0.94ms, 33.6MB)	통과 (0.42ms, 33.7MB)
테스트 15 〉	통과 (0.73ms, 33.6MB)	통과 (0.46ms, 33.6MB)
테스트 16 〉	통과 (0.81ms, 33.6MB)	통과 (0.40ms, 33.5MB)
테스트 17 〉	통과 (3.60ms, 37MB)	통과 (0.61ms, 33.6MB)
테스트 18 〉	통과 (2.73ms, 37MB)	통과 (0.74ms, 33.7MB)
테스트 19 〉	통과 (0.39ms, 33.4MB)	통과 (0.30ms, 33.5MB)
테스트 20 〉	통과 (0.32ms, 33.6MB)	통과 (0.21ms, 33.6MB)
테스트 21 〉	통과 (0.12ms, 33.4MB)	통과 (0.11ms, 33.4MB)
테스트 22 〉	통과 (0.20ms, 33.5MB)	통과 (0.14ms, 33.4MB)
테스트 23 〉	통과 (0.40ms, 33.5MB)	통과 (0.20ms, 33.5MB)
테스트 24 〉	통과 (0.13ms, 33.5MB)	통과 (0.12ms, 33.5MB)
테스트 25 〉	통과 (0.14ms, 33.6MB)	통과 (0.12ms, 33.4MB)
테스트 26 〉	통과 (0.13ms, 33.6MB)	통과 (0.11ms, 33.4MB)
테스트 27 〉	통과 (0.12ms, 33.6MB)	통과 (0.12ms, 33.6MB)
테스트 28 〉	통과 (0.13ms, 33.5MB)	통과 (0.12ms, 33.4MB)
테스트 29 〉	통과 (0.13ms, 33.6MB)	통과 (0.11ms, 33.5MB)
테스트 30 〉	통과 (0.31ms, 33.5MB)	통과 (0.18ms, 33.6MB)
테스트 31 〉	통과 (0.04ms, 33.5MB)	통과 (0.06ms, 33.4MB)
테스트 32 〉	통과 (0.04ms, 33.5MB)	통과 (0.04ms, 33.5MB)
테스트 33 〉	통과 (0.12ms, 33.5MB)	통과 (0.04ms, 33.4MB)
테스트 34 〉	통과 (0.12ms, 33.6MB)	통과 (0.11ms, 33.6MB)
테스트 35 〉	통과 (0.12ms, 33.4MB)	통과 (0.11ms, 33.5MB)
테스트 36 〉	통과 (0.12ms, 33.6MB)	통과 (0.11ms, 33.4MB)
테스트 37 〉	통과 (0.12ms, 33.3MB)	통과 (0.11ms, 33.5MB)
테스트 38 〉	통과 (0.12ms, 33.6MB)	통과 (0.11ms, 33.5MB)