[Javascript] 프로그래머스 - 크기가 작은 부분 문자열

문제 설명

주어진 숫자로 이루어진 문자열 t에서 p와 길이가 같은 부분 문자열을 추출하여, 이 부분 문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 경우의 개수를 구하는 문제입니다.

제한 사항

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

해결 방법

알고리즘: 브루트포스(완전 탐색)

1. p의 길이를 변수 size로 저장합니다.
2. t의 모든 가능한 부분 문자열(길이 size)을 순회하면서, 해당 부분 문자열이 p보다 작거나 같은 경우를 확인합니다.
3. 조건을 만족하는 경우 answer 값을 증가시키고, 최종적으로 answer를 반환합니다.

구현 방법:

• 문자열 t에서 길이 size만큼의 부분 문자열을 slice를 사용하여 추출합니다.
• 비교 연산 시, 문자열을 숫자로 변환하지 않아도 사전순 비교로 문제없이 동작합니다.
• t의 길이가 최대 10,000이므로, O(N) 시간 복잡도로 문제를 해결할 수 있습니다.

시간 복잡도

• t에서 size 길이의 부분 문자열을 탐색하는 과정 O(N)
• 최종 시간 복잡도 O(N)

구현 코드

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

  for (let i = 0; i <= t.length - size; ++i) {
    if (t.slice(i, i + size) <= p) {
      ++answer;
    }
  }

  return answer;
}