[프로그래머스 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
"3141582"	"271"	2
"500220839878"	"7"	8
"10203"	"15"	3

 

---

⌨️ 나의 풀이 (코드)

 

꽤 간단한 문제였지만, 의사코드를 작성해서 실수를 줄이는 것이 좋은 습관이라고 생각한다.

 

1. p의 길이를 측정 
2. t를 순회하며 문자열 내에서 p의 길이만큼의 문자열을 생성 (i.e. p의 길이가 3이라면 해당 인덱스 + 2 까지 범위의 문자열을 변수에 선언 및 할당)
3. 생성된 문자열을 p와 비교해 p보다 작거나 같다면 return 값 +1

 

의사 코드를 기반으로 코드를 작성했다.

 

function solution(t, p) {
  let count = 0;
  for (let i = 0; i <= t.length - p.length; i++) {
    let concat = t[i];

    for (let j = 1; j < p.length; j++) {
      concat += t[i + j];
    }
      
    if(Number(concat) <= Number(p)) {
      count++;
    }
  }
  return count;
}

 

코드는 정상적으로 작동했지만, 좀 더 효율적인 코드가 없을까 고민했다. for 문 안에 for 문의 반복성과 문자열을 계속 순회해야한다는 점 등 보다 효율적으로 개선하기 위한 방안들을 생각해 보았다.

 

1. 문자열을 숫자로 변환할 때, Number() 함수보다 parseInt() 함수를 사용하는 것이 더 효율적 (파싱 최적화 및 필요에 따라 진법-radix- 선택이 가능)

✅ parseInt() 함수를 사용

2. 매번 concat 변수에 t의 일부분을 재조합하여 비교하는 방식은 불필요한 문자열 연산이 많이 발생해 비효율적이므로 시작 위치(인덱스)를 옮겨가며 새로 추가된 문자를 반영하는 방법이 더 나음

✅ t.slice(i, i+ p.length)를 통해 문자열의 일부분을 가져와 불필요한 순회를 삭제

3. 문자열 비교를 위해 매번 비교하기 전에 숫자로 비교하는 과정은 비효율적

✅ 매개변수 p와 그 길이만큼의 문자열을 파싱해 변수에 선언 및 할당

 

개선 방안을 토대로 코드를 재구성 했다.

 

function solution(t, p) {
  let count = 0;
  const pNum = parseInt(p);

  for (let i = 0; i <= t.length - p.length; i++) {
    const tNum = parseInt(t.slice(i, i + p.length));

    if (tNum <= pNum) {
      count++;
    }
  }

  return count;
}

 

테스트 케이스들을 정상적으로 통과했다.